掌握情况

题目 通关
移除链表元素 通过
设计链表 通过（细节问题）
反转链表 通过
两两交换链表中的节点
删除链表倒数第 N 个节点 未通过（快慢指针理解问题）
链表相交 通过
环形链表Ⅱ 未通过（快慢指针理解问题）

移除链表元素

LeetCode 203.移除链表元素

问题

给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

迭代删除

算法思想

  • 用temp表示当前节点。

  • 如果temp的下一个节点不为空且下一个节点的节点值等于给定的val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现： temp.next = temp.next.next

  • 如果temp的下一个节点的节点值不等于给定的val，则保留下一个节点，将temp移动到下一个节点即可。

  • 当temp的下一个节点为空时，链表遍历结束，此时所有节点值等于val的节点都被删除。

  • 由于链表的头节点head有可能需要被删除，因此创建哑节点dummyHead

  • 令dummyHead.next=head，初始化temp=dummyHead，然后遍历链表进行删除操作。最终返回dummyHead.next即为删除操作后的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode removeElements(ListNode head, int val) {
    // 定义虚节点
    ListNode dummyNode = new ListNode(0);
    
    dummyNode.next = head;
    ListNode temp = dummyNode;
    
    // 核心逻辑
    while (temp.next != null) {
        if (temp.next.val == val) {
            temp.next = temp.next.next;
        } else {
            temp = temp.next;
        }
    }
    return dummyNode.next;
}

复杂度分析

时间复杂度$O(n)$，n是链表长度，需要遍历链表一次；

递归删除

算法思想

  • 首先对除了头节点head以外的节点进行删除操作，然后判断head的节点值是否等于给定的val。

  • 如果head的节点值等于val，则head需要被删除，因此删除操作后的头节点为head.next；

  • 如果head的节点值不等于val，则head保留，因此删除操作后的头节点还是head。

  • 上述过程是一个递归的过程。

  • 递归的终止条件是head为空，此时直接返回head。

  • 当head不为空时，递归地进行删除操作，然后判断head的节点值是否等于val并决定是否要删除head。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode removeElements(ListNode head, int val) {
    if (head == null) { // 递归终止条件
        return head;
    }
    // 递归删除下一个节点
    head.next = removeElements(head.next, val);

    /**
        * 判断head节点值是否等于给定的val。
        * 如果节点值等于val，则head需要被删除，因此删除操作后的头节点为head.next；
        * 如果head的节点值不等于val，则head保留，因此删除操作后的头节点还是head。
        * 上述过程是一个递归的过程。
        */
    return head.val == val ? head.next : head;
}

复杂度分析

时间复杂度$O(n)$，n是链表长度，递归过程需要遍历链表一次；空间复杂度$O(n)$，n是链表长度，取决于递归调用栈，最多不会超过n层

设计链表

LeetCode 707.设计链表

问题

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

1
2
3
4
5
6
7
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

单链表

initialize

哨兵节点被用作伪头始终存在，这样结构中永远不为空，它将至少包含一个伪头。MyLinkedList 中所有节点均包含：值 + 链接到下一个元素的指针。

1
2
3
4
5
6
7
8
9
public static class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
}

addAtIndex

  • 找到要插入位置节点的前驱节点。如果要在头部插入，则它的前驱节点就是伪头。

  • 如果要在尾部插入节点，则前驱节点就是尾节点。

  • 通过改变 next 来插入节点。


1
2
toAdd.next = pred.next;
pred.next = toAdd;

deleteAtIndex

  • 找到要删除节点的前驱节点。

  • 通过改变 next 来删除节点。

1
2
// delete pred.next 
pred.next = pred.next.next;

get

从伪头节点开始，向前走 index+1 步。

1
2
3
4
// index steps needed 
// to move from sentinel node to wanted index
for(int i = 0; i < index + 1; ++i) curr = curr.next;
return curr.val;

summery

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public static class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    // Add a node of value val before the index-th node in the linked list.
    // If index equals to the length of linked list, the node will be appended to the end of linked list.
    // If index is greater than the length, the node will not be inserted.
    public void addAtIndex(int index, int val) {

        //If index is greater than the length,
        // the node will not be inserted.
        if (index > size) {
            return;
        }

        // [so weird] If index is negative,
        // the node will be inserted at the head of the list.
        if (index < 0) {
            index = 0;
        }
        ++size;

        //find predecessor of the node to be added
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }

        // node to be added
        ListNode toAdd = new ListNode(val);

        // insertion itself
        toAdd.next = pre.next;
        pre.next = toAdd;
    }


    // Add a node of value val before the first element of the linked list.
    // After the insertion, the new node will be the first node of the linked list.
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    // Append a node of value val to the last element of the linked list.
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    //  Delete the index-th node in the linked list, if the index is valid.
    public void deleteAtIndex(int index) {

        // if the index is invalid, do nothing
        if (index < 0 || index >= size) return;

        size--;

        // find predecessor of the node to be deleted
        ListNode pre = head;
        for(int i = 0; i < index; ++i) {
            pre = pre.next;
        }
        
        // delete pre.next
        pre.next = pre.next.next;
    }

    // Get the value of the index-th node in the linked list. If the index is invalid, return -1.
    public int get(int index) {
        
        // if index is invalid
        if (index < 0 || index >= size) {
            return -1;
        }

        ListNode cur = head;
        
        // index steps needed
        // to move from sentinel node to wanted index
        for (int i = 0; i < index + 1; i++) {
            cur = cur.next;
        }
        
        return cur.val;
    }
}

双链表

initialize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static class MyLinkedList {

    int size;

    //虚拟节点
    DListNode head, tail;

    public MyLinkedList2() {
        size = 0;
        head = new DListNode(0);
        tail = new DListNode(0);
        head.next = tail;
        tail.pre = head;
    }
}

addAtIndex

  • 找到要插入节点的前驱节点和后继节点。

  • 如果要在头部插入节点，则它的前驱结点是伪头。

  • 如果要在尾部插入节点，则它的后继节点是伪尾。

  • 通过改变前驱结点和后继节点的链接关系添加元素。

1
2
3
4
toAdd.prev = pred
toAdd.next = succ
pred.next = toAdd
succ.prev = toAdd

deleteAtIndex

  • 找到要删除节点的前驱结点和后继节点。
  • 通过改变前驱结点和后继节点的链接关系删除元素。

1
2
pred.next = succ
succ.prev = pred

get

  • 通过比较 index 和 size - index 的大小判断从头开始较快还是从尾巴开始较快。
  • 从较快的方向开始。

1
2
3
4
5
6
7
8
9
// choose the fastest way: to move from the head
// or to move from the tail
ListNode curr = head;
if (index + 1 < size - index)
  for(int i = 0; i < index + 1; ++i) curr = curr.next;
else {
  curr = tail;
  for(int i = 0; i < size - index; ++i) curr = curr.prev;
}

summery

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
public class MyLinkedList {
    
    int size;
    
    // dummyNode
    DListNode head, tail;

    public MyLinkedList() {
        size = 0;
        head = new DListNode(0);
        tail = new DListNode(0);
        head.next = tail;
        tail.pre = head;
    }

    // Get the value of the index-th node in the linked list. If the index is invalid, return -1.
    public int get(int index) {
        
        // if index is invalid
        if (index < 0 || index >= size) return -1;

        // choose the fastest way: to move from the head
        // or to move from the tail
        DListNode cur = head;
        if (index + 1 < size - index)
            for(int i = 0; i < index + 1; ++i) cur = cur.next;
        else {
            cur = tail;
            for(int i = 0; i < size - index; ++i) cur = cur.pre;
        }

        return cur.val;
    }

    // Add a node of value val before the first element of the linked list.
    // After the insertion, the new node will be the first node of the linked list.
    public void addAtHead(int val) {
        DListNode pre = head, succ = head.next;

        ++size;
        DListNode toAdd = new DListNode(val);
        toAdd.pre = pre;
        toAdd.next = succ;
        pre.next = toAdd;
        succ.pre = toAdd;
    }

    // Append a node of value val to the last element of the linked list.
    public void addAtTail(int val) {
        DListNode succ = tail, pre = tail.pre;

        ++size;
        DListNode toAdd = new DListNode(val);
        toAdd.pre = pre;
        toAdd.next = succ;
        pre.next = toAdd;
        succ.pre = toAdd;
    }
    
    // Add a node of value val before the index-th node in the linked list.
    // If index equals to the length of linked list, the node will be appended to the end of linked list.
    // If index is greater than the length, the node will not be inserted.
    public void addAtIndex(int index, int val) {
        
        // If index is greater than the length,
        // the node will not be inserted.
        if (index > size) return;

        // [so weird] If index is negative,
        // the node will be inserted at the head of the list.
        if (index < 0) index = 0;

        // find predecessor and successor of the node to be added
        DListNode pre, succ;
        if (index < size - index) {
            pre = head;
            for(int i = 0; i < index; ++i) pre = pre.next;
            succ = pre.next;
        }
        else {
            succ = tail;
            for (int i = 0; i < size - index; ++i) succ = succ.pre;
            pre = succ.pre;
        }

        // insertion itself
        ++size;
        DListNode toAdd = new DListNode(val);
        toAdd.pre = pre;
        toAdd.next = succ;
        pre.next = toAdd;
        succ.pre = toAdd;
    }

    // Delete the index-th node in the linked list,
    // if the index is valid.
    public void deleteAtIndex(int index) {
        
        // if the index is invalid, do nothing
        if (index < 0 || index >= size) return;

        // find predecessor and successor of the node to be deleted
        DListNode pre, succ;
        if (index < size - index) {
            pre = head;
            for(int i = 0; i < index; ++i) pre = pre.next;
            succ = pre.next.next;
        }
        else {
            succ = tail;
            for (int i = 0; i < size - index - 1; ++i) succ = succ.pre;
            pre = succ.pre.pre;
        }

        // delete pred.next
        --size;
        pre.next = succ;
        succ.pre = pre;
    }

}
public class DListNode {
    int val;
    DListNode next;
    DListNode pre;

    public DListNode(int val) {
        this.val = val;
    }
}

反转链表

LeetCode 206.反转链表

问题

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 头插法
public ListNode reverseList(ListNode head) {
    
    // 添加虚拟节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 定义哨兵节点
    ListNode sentinel;
    
    // 断链
    dummy.next = null;
    
    while (head != null) {
        sentinel = head;
        head = head.next;
        sentinel.next = dummy.next;
        dummy.next = sentinel;
    }
    
    return dummy.next; 
}

迭代法

算法思想

  • 假设链表为$1→2→3→∅$，我们想要把它改成 $∅←1←2←3$

  • 在遍历链表时，将当前节点的next指针改为指向前一个节点

  • 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点

  • 在更改引用之前，还需要存储后一个节点。最后返回新的头引用 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 迭代法
public ListNode reverseList(ListNode head) {
    // 前驱节点
    ListNode pre = null;
    // 当前节点
    ListNode cur = head;

    while (cur != null) {
        // 保存当前节点的后继
        ListNode next = cur.next;
        // 将当前节点的后继指向其前驱
        cur.next = pre;
        // pre后移
        pre = cur;
        // 当前节点指向原链表下一个位置
        cur = next;
    }

    return pre;
}

递归法

算法思想

假设链表：$n1\rightarrow … \rightarrow n{k-1} \rightarrow nk \rightarrow n{k+1}\rightarrow … \rightarrow nm \rightarrow ∅$
若从节点$n{k+1}$到$nm$已经被反转，而我们正处于$n_k$
$n_1\rightarrow … \rightarrow n{k-1} \rightarrow nk \rightarrow n{k+1}\leftarrow … \leftarrow nm$
我们希望 $n{k+1}$ 的下一个节点指向 $n_k$，所以 $n_k.next.next=n_k$，需要注意的是$n_1$的下一个节点必须指向$∅$，否则会产生环

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
33
34
35
36
// 递归法
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        /**
            直到当前节点的下一个节点为空时返回当前节点
            由于5没有下一个节点了，所以此处返回节点5
            */
        return head;
    }
    //递归传入下一个节点，目的是为了到达最后一个节点
    ListNode newHead = reverseList(head.next);
    /**
        第一轮出栈，head为5，head.next为空，返回5
        第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
        把当前节点的子节点的子节点指向当前节点
        此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
        此时链表为1->2->3->4<-5
        返回节点5
        第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
        此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
        此时链表为1->2->3<-4<-5
        返回节点5
        第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
        此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
        此时链表为1->2<-3<-4<-5
        返回节点5
        第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
        此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
        此时链表为1<-2<-3<-4<-5
        返回节点5
        出栈完成，最终头节点5->4->3->2->1
    */
    head.next.next = head;
    head.next = null;
    return newHead;
}

两两交换链表中的节点

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

问题

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

迭代法

算法思想

由于将链表划分成若干组，每组两个，每组内进行局部翻转，因此可以先计算出需要将链表分成几组，然后再进行翻转，修补操作，直到整个链表达到相应要求，LeetCode测试样例中的链表往往不带虚拟节点，我们可以构造虚拟节点然后完成相应算法。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 迭代法
public ListNode swapPairs(ListNode head) {

    // 构造虚拟节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // 计算链表长度
    int len = 0;
    // 定义哨兵节点p
    ListNode p = head;
    // 定义每组翻转的最后一个节点
    ListNode tail = null;
    // 定义哨兵节点q
    ListNode q = null;
    // 定义每次翻转时的临时头节点
    ListNode s = null;

    // 计算链表长度
    if (p != null) {
        len++;
        p  = p.next;
    }

    // p重新指向第一个元素节点
    p = dummy.next;
    // s、q指向虚拟节点
    s = dummy;
    q = dummy;

    // 外部循环用于控制翻转次数
    for (int i = 0; i < len / 2; i++) {

        // tail用于记录每组翻转后的最后一个节点
        tail = p;
        // 断链操作
        s.next = null;
        // 内部循环用于控制每组的局部翻转 (此时每组只有两个节点)
        for (int j = 0; j < 2; j++) {
            // 即将操作该节点
            q = p;
            // p此时充当哨兵的作用
            p = p.next;
            
            // 经典头插法
            q.next = s.next;
            s.next = q;
        }
        
        // 修补断链
        tail.next = p;
        // s指向的位置，供下一次翻转
        s = tail;
    }
    return dummy.next;
}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 递归法
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode oneNode = head;
    ListNode twoNode = oneNode.next;
    ListNode threeNode = twoNode.next;

    twoNode.next = oneNode;
    oneNode.next = swapPairs(threeNode);

    return twoNode;
}

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

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

问题

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


1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

算法思想

快慢指针经典应用。让快指针指向第一个元素节点，慢指针指向哑节点，快指针先移动，直到快慢指针相距n步，慢指针开始移动，此时两个指针同步移动，当快指针走到null时，快慢指针差n个节点，开始删除操作

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
public ListNode removeNthFromEnd(ListNode head, int n) {

    // 建立虚拟节点
    ListNode dummy = new ListNode(0, head);
    // 快指针指向第一个元素节点
    ListNode fast = head;
    // 慢指针指向虚拟节点
    ListNode slow = dummy;

    // 快指针先移动。直到两个指针步长差距为n
    for (int i = 0; i < n; ++i) {
        fast = fast.next;
    }

    // 完成上述操作，慢指针与快指针同步移动
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 此时快指针超前慢指针n步
    slow.next = slow.next.next;
    ListNode ans = dummy.next;

    return ans;
    }

链表相交

面试题 02.07. 链表相交

问题

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构

暴力法

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 暴力法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 定义双指针
    ListNode curA = headA;
    ListNode curB = headB;
    // 定义len
    int lenA = 0, lenB = 0;

    // lenA
    while (curA != null) {
        lenA++;
        curA = curA.next;
    }

    // lenB
    while (curB != null) {
        lenB++;
        curB = curB.next;
    }

    // 重新指向头节点
    curA = headA;
    curB = headB;

    // curA指向最长链表的头节点
    if (lenA < lenB) {
        // 交换lenA与lenB
        int tempLen = lenA;
        lenA = lenB;
        lenB = tempLen;
        
        // 交换curA和curB
        ListNode tempNode = curA;
        curA = curB;
        curB = tempNode;
    }
    
    // 长度差
    int gap = lenA - lenB;
    
    // 让curA和curB处在同一起点
    while (gap-- > 0) {
        curA = curA.next;
    }
    
    // 双指针同步移动
    while (curA != null) {
        if (curA == curB) {
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return  null;
}

哈希法

  • 判断两个链表是否相交，可以使用哈希集合存储链表节点。

  • 首先遍历链表headA，并将链表headA中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：

  • 如果当前节点不在哈希集合中，则继续遍历下一个节点；

  • 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。

  • 如果链表headB中的所有节点都不在哈希集合中，则两个链表不相交，返回null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 哈希法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> visited = new HashSet<>();
    ListNode temp = headA;
    
    // 将A链表放入哈希表中
    while (temp != null) {
        visited.add(temp);
        temp = temp.next;
    }
    
    temp = headB;
    
    // 遍历B链表
    while (temp != null) {
        if (visited.contains(temp)) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
}

双指针法

  • 每步操作需要同时更新指针pA和pB。

  • 如果指针pA不为空，则将指针pA移到下一个节点；如果指针pB不为空，则将指针pB移到下一个节点。

  • 如果指针pA为空，则将指针pA移到链表headB的头节点；如果指针pB空，则将指针pB移到链表headA的头节点。

  • 当指针pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 双指针法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    ListNode pA = headA, pB = headB;

    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : headB.next;
    }
    return pA;
}

环形链表Ⅱ

LeetCode 142.环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置 (索引从 0 开始)。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
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
public ListNode detectCycle(ListNode head) {
    
    // 违规条件
    if (head == null) {
        return null;
    }
    
    // 定义快慢指针
    ListNode slow = head, fast = head;
    
    while (fast != null) {
        slow = slow.next;
        if (fast.next != null) {
            fast = fast.next.next;
        } else {
            return null;
        }
        // 如果有环，快指针一定会追上慢指针
        if (fast == slow) {
            fast = head;
            // 同步移动，直到相遇，则为入环口
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
}

总结

  • 哈希辅助存储结构
  • 快慢指针思想