【链表专题】刷题心得

一、虚拟头节点的选取

一般来说，如果对链表进行的操作有可能改变head节点，比如删除head或者移动head，可以对边界条件进行判空。但这种情况的一般做法是：我们创建一个虚拟头节点，无论head如何变化，虚拟头节点是始终存在的。

虚拟头节点的运用十分广泛，我们来看一看具体的运用。

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

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思考

一般来说，单链表的删除操作，需要知道该节点的pre，让pre.next = pre.next.next。

可能会删除头部，可以使用虚拟头节点化解。
双指针，快指针先走n步，慢指针先不动。
两者同时向后走，当快指针指向最后一个节点，慢指针正好走到倒数第N+1个节点。
删除慢指针的下一个节点：slow.next = slow.next.next;。

虚拟头节点

头节点head将会发生变化的时候，头节点将会派上用场。

一、普通创建一个节点即可。ListNode dummy = new ListNode(-1);

二、注意让虚拟头节点和真实头节点产生联系。dummy.next = head;

三、最后返回的值是虚拟头节点的next，因为头节点可能存在被删除的情况：return dummy.next;

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;		//虚拟节点和head联系起来
        ListNode slow = dummy, fast = dummy; //快慢指针同时指向虚拟头
        while( n-- > 0){
            fast = fast.next; //快指针先走n步
        }
        while(fast.next != null){ //同时向后移动
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next; //删除目标节点
        return dummy.next;       //返回dummy.next
    }
}

二、使用双指针找到指定位置的节点

同样的，双指针的做法通常在链表题中也比较常见，可以经常看到有快慢指针解决寻找位置为k的节点【比如上面那题】，判断链表成环等问题。除了快慢指针，可能还有每次列出一对节点，进行交换或者其他操作，也是巧妙利用了指针。

61. 选转链表

61. 旋转链表

难度中等328

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思考：

k%链表长度
双指针找到倒数第k+1的位置。
最后一个节点指向第一个节点，倒数第k+1个节点指向null，head指向倒数第k个点。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        int n = 0;
        for(ListNode p = head; p != null; p = p.next) n++; //链表总结点数
        k %= n; //每次要移动尾部的k个数到头部
        ListNode slow = head, fast = head;
        while(k -- > 0) fast = fast.next; 
        while(fast.next!= null){
            fast = fast.next;
            slow = slow.next;
        }//双指针找到倒数第k+1的位置
        fast.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }
}

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        for(ListNode p = dummy; p.next != null && p.next.next != null;){
            ListNode a = p.next,b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dummy.next;
    }
}

三、反转链表的相关问题

206. 反转链表

题目描述

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

迭代做法

我们的目标就是：让最开始的节点指向空，第二个节点指向第一个节点……最后一个节点指向倒数第二个节点，最后返回最后一个节点。

如何实现呢，其实思路很简单：

我们需要每次用两个指针拿出两个两个节点【当然最开始的两个节点我们把它看成null和1】，我们用pre表示第一个节点，用curr表示第二个节点，翻转关系表示为：curr.next = pre；
我们每次将指针同时向后移动，表示处理下一对节点，pre向后移动表示为：pre = curr，但curr怎么向后移呢，此时curr的next指针已经指向pre，也就是说第一步的时候，curr的next指针已经丢失，这样是显然不行的。
这时，我们就需要用到链表中一个非常常用的手段，将curr.next指针暂存起来，ListNode next = curr.next，curr向后移动就可以表示为：curr = next；
终止条件是什么呢，其实链表的题目画一画图基本就出来了，当curr指向null的时候，pre正好指向最后一个节点，也就是本题需要的新头，返回pre即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, curr = head, next = null;
        while( curr!=null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;

        }
        return pre;
    }
}

【第二个迭代做法】

思路大致差不多，不解释了，直接画图。

    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode p = head, q = p.next;
        while(q!=null){
            ListNode n = q.next;
            q.next = p;
            p = q;
            q = n;
        }
        head.next = null;
        return p;
    }

92. 反转链表 II

题目描述

92. 反转链表 II

该题解参考自Acwing yxc：https://www.acwing.com/solution/content/174/

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思考

特判：如果m == n，表示无需反转，直接return head即可。
这个反转过程中，头节点可能会被改变，我们使用虚拟头节点化解即可。
反转的过程如何？
- 确定我们需要的节点位置
  - 设反转段为[b,d]，反转段的迁移节点为a，反转段的后一节点为c。
  - a就是从虚拟节点走m-1步的位置，d就是从虚拟节点走n步的位置。
  - 那么相应的，b = a.next; c = d.next。
- 反转[b,d]，如何实现呢？这个问题转化为将head为b的链表，以d为结尾的链表的反转问题，参考之前的做法，我们可以如下做：
  - 双指针每次取出两个节点，p和q，p = b，q = p.next。
  - 使用临时节点o存储q的下一个位置，保存一下。o = q.next;
  - 让q的next指向p。q.next = p;
  - p和q同时向后移。p = q; q = o;
  - 终止条件在于：q这个节点是不是已经到头了，是不是走到了c的位置。
- 此时链表其实已经被分为三段，我们需要拼接这三段就可以。
  - b.next = c;
  - a.next = d;

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy, d = dummy;
        for(int i = 0; i < m - 1; i++) a = a.next;
        for(int i = 0; i < n ; i ++) d = d.next;

        ListNode b = a.next;
        ListNode c = d.next;

        for(ListNode p = b, q = p.next; q!=c;){
            ListNode o = q.next;
            q.next = p;
            p = q;
            q = o;
        }
        b.next = c;
        a.next = d;
        return dummy.next;
    }
}

链表中元素的删除操作

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

思考：

将要删除的节点伪装成下一个节点，然后将下一个节点删除：
- 值变成下一个节点的值。
- next指向下一个节点的next。

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

思考：

加入链表本身为空，返回，做一个特判。
假设保留第一个节点，让curr指向head。
判断下一个节点的取值和curr取值的关系：
- 如果相等，就删除下一个节点，即curr.next = curr.next.next
- 如果不相等，则让curr向后移一位，即curr = curr.next
终止条件是curr.next==null。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode curr = head;
        while(curr.next !=null){
            if(curr.next.val == curr.val){
                curr.next = curr.next.next;
            }else{
                curr = curr.next;
            }
        }
        return head;
    }
}

移除未排序链表中的重复节点

示例1:

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

这时，我们就需要使用存储结构存储一下，这里可以使用set。

    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null) return head;
        ListNode curr = head;
        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        while( curr.next != null){
            int nextVal = curr.next.val;
            if(set.add(nextVal)) curr = curr.next;
            else curr.next = curr.next.next;
        }
        return head;
    }

链表成环或相遇问题

141. 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思考：

判断链表成环是一类典型的题目：通常可以使用快慢指针的做法或者利用哈希表求解：

哈希表

哈希表的思路简单易懂。

    //利用set
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;

    }

时间复杂度：O(N)，遍历一遍链表消耗的时间。

空间复杂度：O(N)，额外创建哈希表。

快慢指针

哈希表最差情况下，需要长度n空间的消耗，而快慢指针的做法利用环形链表的特性，可以将空间复杂度降至O(N)。

如果链表无环，那么快指针最终会率先指到null。fast == null || fast.next.next == null
如果链表忧患，快指针会沿着环，最终两者相遇，且一定会相遇。

    //双指针
    public boolean hasCycle2(ListNode head) {

        if(head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while( slow != fast) {
            if(fast == null || fast.next == null) return false;//无环
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

时间复杂度：

无环：时间取决于快指针移动的长度，也就是O(N)。
有环：O(N+K)，环形部分长度+非环形部分长度。

空间复杂度：

O(1)，只用了两个指针。

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思考：

类似的做法，依然有常见的两种做法，哈希和双指针。

哈希表

直接上代码了，其实差不多。

    //利用set
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

时间复杂度：O(N)，遍历一遍链表消耗的时间。

空间复杂度：O(N)，额外创建哈希表。

快慢指针

这道题真的太经典了，解法过于巧妙，但真正要推理证明，还是不容易的。这里参考Krahets的解法

快慢指针走的时候，遇到的几种情况：

快指针走过链表末端，无环。
假设fast == slow第一次在环中相遇，fast和slow的步数关系为【可以参考下面的图】：
- 假设非环部分长度为a，环形部分长度为b，快指针走了f步，慢指针走了s步。
- 快指针是慢指针的两倍，(f = 2s)。
- 快指针比慢指针多走了n个环的长度，(f = s+nb)。
- 得(f = 2nb, s = nb)，快慢指针分别走了2n，n个环的周长。
因此，从head出发，走到链表环入口节点的步数是(k = a + nb)。慢指针此时已经走了nb步，此时让快指针指向head，和slow指针一起移动a步，直到第二次相遇，就可以找到入口节点。

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;//链表无环
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;//第一次相遇
        }
        fast = head; //让fast指向head
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;//第二次相遇
    }

时间复杂度：O(N)，N = a + b

空间复杂度：O(1)

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

假设(L_A)是A非交集部分的长度，(L_B)是B非交集部分的长度， (C)是交集部分的长度，以下关系成立。

(L_A + C + L_B = L_B + C + L_A)

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode n1 = headA;
        ListNode n2 = headB;
        
        while(n1 != n2){
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }