【数据结构】链表2：双指针_一个链表有几个指针

判断链表是否有环

方法一：哈希表

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();
        while(head!=null){
            //判断哈希表中是否存在该节点
            if(nodes.contains(head)){
                return true;
            }else{
                //向哈希表中添加节点
                nodes.add(head);
            }
            head=head.next;
        }
        return false;
    }      
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：快慢指针

想象有两个指针，一个快指针：每次移动两步；一个慢指针：每次移动一步。

• 如果没有环，快指针将停在链表的末尾。
• 如果有环，快指针最终将与慢指针相遇。
  （无论快慢指针初始在哪，最后总能相遇。但初始化时要注意循环条件）

使用快慢指针很容易解决这道题，但要注意避免空指针异常：java.lang.NullPointerException：如果fast=null，那么使用 fast.next 会抛出空指针异常，所以在赋值前，需要进行判断。

public boolean hasCycle(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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

环形链表II

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

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

方法一：使用哈希表

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();
        while(head!=null){
            //判断哈希表中是否存在该节点
            if(nodes.contains(head)){
                //若表中已存在，说明是入环的第一个节点。返回该节点
                return head;
            }else{
                //向哈希表中添加节点
                nodes.add(head);
            }
            head=head.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：Floyd 算法 (双指针)

LeetCode官方题解

阶段一：找到相遇点

设环的节点长度为 $C$，非环节点长度为 $F$。环中的节点从 0 到 $C-1$编号，非环节点从 $-F$ 到 $-1$ 编号，
快指针和慢指针同时从第一个节点出发，每次移动慢指针一步、快指针两步。如果快慢指针相遇，那么一定有环，且相遇节点为 $C-h$ 节点，其中有$h=(F\mathrm{m}\mathrm{o}\mathrm{d}C)-1$

推导：

1. $F$次迭代后：快指针遍历了 2F 个节点，记此时指向的节点为$h$。
2. 继续迭代 $C-h$ 次：慢指针显然指向第 $C-h$ 号节点。快指针从 $h$号节点出发遍历了 $2(C-h)$个节点
   $h+2(C-h)=2C-h$ ，$2C-h$ mod $C$后正好为 $C-h$。

总结

---

所以：如果列表是有环的，经过 $F+C-h$ 次循环后，快指针和慢指针最后会同时指向同一个节点$C-h$。（关于计算环中的索引，使用 mod 就好了）

阶段二：找到入口
初始化指针，ptr1 指向链表的头， ptr2 指向相遇点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口

推导 $F=b$：

$$\begin{array}{rl}2\cdot \text{ distance}(\text{fast})& =\text{distance}(\text{slow})\\ 2(F+a)& =F+a+b+a\\ 2F+2a& =F+2a+b\\ F& =b\end{array}$$

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        //阶段一：找到相遇节点
        ListNode nodeEnd=meetCycle(head);
        //阶段二：找到环的第一个节点
        if(nodeEnd==null) return null;
        ListNode nodeStart=head;
       // ListNode nodeEnd=nodeMeet;
        while(nodeStart!=nodeEnd){
            nodeStart=nodeStart.next;
            nodeEnd=nodeEnd.next;
        }
        return nodeStart;
    }

    private ListNode meetCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast!= null&& fast.next != null) {   //注意：是&&
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow){
                return slow;
            }
        }
        return null;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

个人曾经的坑

1、
        //阶段二
        // if(nodeEnd!=null){
        //     ListNode nodeStart=head;
        //    // while(nodeStart!=nodeEnd){ 不能这么写，有可能他们的相遇点就是入环第一个节点
        //         nodeStart=nodeStart.next;
        //         nodeEnd=nodeEnd.next;
        //         if(nodeStart==nodeEnd){
        //             return nodeStart;
        //         }
        //     }
        // }
        // return null;
2、       
 while (fast!= null&& fast.next != null) {   //注意：是&&
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

相交链表/剑指52. 两个链表的第一个公共节点

编写一个程序，找到两个单链表相交的起始节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
1
2
3
4
5

方法一：双指针法(最优)

原理：使用双指针。注意没有交点的情况。
指针 1 遍历链表 A+B，指针 2 遍历链表 B+A，1/2 要能指向自己的null节点，指向了自己的null 节点后才指向 B/A 的头节点（不然停不下来）
即 指针1==指针2 一定会成立（要么指向同一节点，要么都为空）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA=headA;
        ListNode ptrB=headB;
        while(ptrA!=ptrB){ //有相交节点会指向相交节点；没有则指向空 
            ptrA= (ptrA==null)? headB:ptrA.next; //遍历A+B，注意这里，ptrA != null 才指向 B的头节点
            ptrB= (ptrB==null)? headA:ptrB.next; //遍历B+A
        }
        return ptrA;
    }
}
1
2
3
4
5
6
7
8
9
10
11

方法二：使用额外空间

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //方法一：使用数组存放其中一个链表
        if(headA==null||headB==null){
            return null;
        }

        List<ListNode> list=new ArrayList<ListNode>();
        for(ListNode t=headA; t!=null;t=t.next){
            list.add(t);
        }

        for(ListNode b=headB; b!=null;b=b.next){
            if(list.contains(b)){
                return b;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

方法一：两次遍历

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return head;
        }
        //添加一个哑结点作为辅助
        //哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //遍历链表得到链表长度
        ListNode p = head;
        int len=0;
        while(p!=null){
            len++;
            p=p.next;
        }
        //找到倒n节点的前一个节点,指针p走len-n-1 步
        p = dummy;
        len-=n;
        while(len>0){
            p=p.next;
            len--;    
        }
        p.next=p.next.next;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

复杂度分析：

• 时间复杂度：$O(L)$，该算法对列表进行了两次遍历，首先计算了列表的长度 $L$ 其次找到第 $(L-n)$ 个结点。 操作执行了 $2L-n$ 步，时间复杂度为 $O(L)$。

• 空间复杂度：$O(1)$，指针只用了常量级的额外空间。

个人的坑

注意极端情况的处理：
如列表中只含有一个结点，或需要删除列表的头部，此时从第二个节点返回即可。
所以盲指针dummy.next = head，否则删除列表的头部时找不到其前置节点
1
2
3

方法二：一次遍历（双指针）

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null) return head;

        //头节点同样保存了信息。
        //新增一个前置节点，是为了方便处理删除头结点的情况
        ListNode dummy = new ListNode(0);
        dummy.next=head;

        //使用双指针
        ListNode slow=dummy;
        ListNode fast=dummy;
        //fast指针要先走n+1步
        while(n>=0){
            fast=fast.next;
            n--;
        }
        //当fast指向尾节点的下一个null时，slow正好指向倒n+1节点
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

复杂度分析：

• 时间复杂度：$O(L)$，该算法对含有 $L$ 个结点的列表进行了一次遍历。因此时间复杂度为 $O(L)$。

• 空间复杂度：$O(1)$。

小结

模板

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：

---

1. 在调用 next 字段之前，始终检查节点是否为空。

获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

2. 仔细定义循环的结束条件。

运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。

复杂度分析：

---

空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 $O(1)$。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。

如果没有循环，快指针需要 $N/2$ 次才能到达链表的末尾，其中 N 是链表的长度。
如果存在循环，则快慢指针相遇需要 $F+C-h$ 次循环,显然，$F+C-h<=N$ 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 $O(N)$。

自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，请考虑最糟糕的情况。