【算法社区】链表之反转链表、删除链表的倒数第 N 个结点

简介: 字节跳动企业题库,链表系列,那我们从出题频率最高刷到最低,题目有206. 反转链表 、19. 删除链表的倒数第 N 个结点

image.png

前言:📫 作者简介:小明java问道之路,专注于研究计算机底层,就职于金融公司后端高级工程师,擅长交易领域的高安全/可用/并发/性能的设计和架构📫

🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆

🔥 如果此文还不错的话,还请👍关注点赞收藏三连支持👍一下博主哦

本文导读

字节跳动企业题库,链表系列,因为有leetcode会员能看到企业出题频率,那我们从出题频率最高刷到最低,题目有206. 反转链表 、19. 删除链表的倒数第 N 个结点


206. 反转链表

【简单】【题目描述】给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]

示例 2:输入:head = [1,2] 输出:[2,1]

示例 3:输入:head = [] 输出:[]

这道题是一到老生常谈的题目,对于熟悉链表的同学来说是秒杀的,我们分递归和迭代两种方法解题

【迭代、递归】图解:

image.png

代码详解,逐行注释:

public ListNode reverseList(ListNode head) {  /*迭代法*/
        ListNode prev = null;  // 1 对于上图解析,先设置两个结点
        ListNode curr = head;  // 2
        while (curr != null) { 
            ListNode next = curr.next;  // 3 反转
            curr.next = prev;           // 4
            prev = curr;   // 5 向前移动
            curr = next;   // 6
        }
        return prev;
    }
    public ListNode reverseList(ListNode head) {  /*递归法*/
        if (head == null || head.next == null) { // 递归停止条件
            return head;
        }
        ListNode newHead = reverseList(head.next); // 递归
        head.next.next = head;  // 1 将后一位指向前一位
        head.next = null;       // 2 断开前一位的next指针
        return newHead;
    }

image.gif

 

19. 删除链表的倒数第 N 个结点

【中等】【题目描述】给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

示例 1:输入:head = [1,2,3,4,5], n = 2输出:[1,2,3,5]

示例 2:输入:head = [1], n = 1输出:[]

示例 3:输入:head = [1,2], n = 1输出:[1]

这是所有大厂爱考的链表题目之一,对于熟悉链表的同学来说是秒杀的,我们用暴力法、快慢指针(双指针)法解题

image.png

代码详解,逐行注释:

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);    // 保留的头节点
        int length = getLength(head);  // 获取链表长度
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) { // 遍历到 L-n+1的位置
            cur = cur.next;
        }
        cur.next = cur.next.next;   // 删除节点
        ListNode ans = dummy.next;  // 返回保留的头节点
        return ans;
    }
    public int getLength(ListNode head) { /*遍历一遍,计算链表长度*/
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);  // 保留的头节点
        ListNode first = head;      // 快指针
        ListNode second = dummy;    // 慢指针
        for (int i = 0; i < n; ++i) // 快指针先走的n的位置
            first = first.next;
        while (first != null) {     // 同时向后移动
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next; // 删除节点
        ListNode ans = dummy.next;      // 返回保留的头节点
        return ans;
    }

image.gif


相关文章
|
19天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
52 1
|
24天前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
22天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
15天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
28 0
|
22天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
24天前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
3月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
49 5
|
4月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
32 1
【数据结构OJ题】链表中倒数第k个结点