06 |「链表」必刷题_球友工科男小y

前言

前言：刷「链表」高频面试题。

一. 基础回顾

详细介绍参考 04 讲： 链表简析（点击链接直达）

1. 增删改查

结构：$1$->$2$->$3$->NULL，链表是 指向型结构 。
查找：随机访问的时间复杂度是 $O(n)$。
增删：删除和插入元素的时间复杂度都是 $O(1)$ 。

---

2. 虚拟头节点

1）头节点

对于链表，给我们一个链表时，我们拿到的是头节点（head） 。如果没有头结点证明整个链表为空 NULL，如果已有头结点则证明链表不为空。

2）为什么需要虚拟头结点

针对链表头结点 （head）为空和不为空需要执行不同的操作。每次对应头结点都需要单独处理，所以使用头结点的技巧，可以解决这个问题。

例如，删除链表中的某个节点必须要找到前一个节点才能操作。这就造成头结点的尴尬，对于头结点来说没有前一个节点。

如果链表为空(head = null)，那么 访问 null.val 与 null.next 会出错。为了避免这种情况，增加一个虚拟头结点（dummy）可以统一操作，不用关心头结点是否为空。这样 dummy.next = null，避免直接访问空指针。

其中 dummy 的值 （val）常用 -1 表示，next 指向 头结点（head）。

---

3. 链表的遍历

// 增加虚拟头节点的链表遍历
dummy; dumm->next = head; p = dummy;
while (p) 
{

}
1
2
3
4
5
6

// 没有虚拟头结点的链表遍历
head;
while (head)
{
    head = head->next;
}
1
2
3
4
5
6

---

二. 高频面试题

1. 例题

例题1：LeetCode 206 反转链表

1）题目链接

原题链接：反转链表（点击链接直达）

2） 算法思路

• 明确：修改几条边，修改哪几条边，注意是修改 n 条边；
• 操作：将当前节点的 next 指针改为指向前一个节点（last）；
• 维护：双链表可以通过 pre 指针访问前一个节点。针对单链表，没有 pre 指针无法访问前一个节点（last），需要新开一个变量维护前一个节点（last）；
• 边界：针对头结点（head）没有前一个节点，创建 last 并赋为 NULL；

3）源码剖析

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    	if (!head || !head->next) return head;
        ListNode* last = nullptr;			//（1）
        ListNode* cur = head;				//（2）
        while (cur)							//（3）
        {
            ListNode* next = cur->next;		//（4）
            cur->next = last;				//（5）
            last = cur;						//（6）
            cur = next;						//（7）
        }
        return last;						//（8）
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• （1）/（2）初始化变量 last 和 cur， last 指向上一个节点，cur 指向当前节点；
• （3）修改每条边，需要循环遍历访问每个节点；
• （4）修改一条边时，先保存当前节点（cur）的下一个节点（next），防止丢失；
• （5）修改一条边；
• （6）/（7）last 和 cur 分别向后移动一位；
• （8）返回反转后链表的头结点。当 cur 停下时指向原链表的 NULL，此时 last 指向反转后链表的头结点；

4）时间复杂度

        $O(n)$

---

例题2：LeetCode 92 反转链表II

1）题目链接

原题链接：反转链表（点击链接直达）

2） 算法思路

• 将 tmp 节点移动到 left-1 的位置处；
• 反转 [left, right] 部分的节点。从 left 位置开始反转，反转 right-left 次；
• 调整剩余部分节点的指向；
• 返回头结点；

3）源码剖析

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
    	if (left == right) return head;							//（1）
        ListNode* dummy = new ListNode(-1);						//（2）
        dummy->next = head;
        ListNode* tmp = dummy;
        for (int i = 0; i < left - 1; i ++) tmp = tmp->next;	//（3）
        														//（4）						
        ListNode* pre = tmp->next;
        ListNode* cur = pre->next;
        for (int i = 0; i < right - left; i ++) 
        {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        														//（5）											
        tmp->next->next = cur;
        tmp->next = pre;

        return dummy->next;										//（6）
    }
};
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

• （1）left=right 证明只有一个头结点；
• （2）dummy 为哨兵节点。因为 left 可能在 head 位置，故添加哨兵节点；
• （3）将 tmp 节点移动到 left-1 的位置；
• （4）(4)- (5)之间的代码为反转 [left, right] 部分的节点，逻辑同上题；
• （5）(5)-(6) 之间的代码为调整其它节点的指向。如示例1，2 的 next 指向 5，1的 next 指向 4；
• （6）返回链表头节点；

4）时间复杂度

        $O(n)$

---

例题3：LeetCode 203 移除链表元素

1）题目链接

原题链接：移除链表元素（点击链接直达）

2）遍历做法

• 增加 dummy 哨兵节点的目的是统一操作，少写特判断头结点（head）是否为空。

  // 不增加哨兵节点dummy
  if (!head) {
  	return head;
  } else {
  
  }
  1
  2
  3
  4
  5
  6

  // 增加哨兵节点dummy
  class Solution {
  public:
      ListNode* removeElements(ListNode* head, int val) {
          ListNode* dummy = new ListNode(-1);
          dummy->next = head;
          ListNode* p = dummy;
  
          while (p->next)
          {
              if (p->next->val == val) p->next = p->next->next;
              else p = p->next;
          }
  
          return dummy->next;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

3）递归做法

if (!head) return head;
head->next = removeElements(head->next, val); 
return head->val == val? head->next : head;
1
2
3

3）时间复杂度

        $O(n)$

---

2. 习题

习题1：LeetCode 19 删除链表的第N个节点

1）题目链接

原题链接： 删除链表的第N个节点（点击链接直达）

2） 算法思路

纸上画图实际模拟一遍即可。

3）源码剖析

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);			//（1）
        dummy->next = head;
        ListNode* p = dummy, *q = dummy;
        for (int i = 0; i < n; i ++) p = p->next;	//（2）
        while (p->next != nullptr) 					//（3）
        {
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;					//（4）

        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• （1）定义虚拟头结点 dummy，不用考虑头结点的特殊情况；
• （2）p 指针先走 n 步；
• （3）p 指针和 q 指针同时走，直到 p 指针走到最后一个节点，两指针都停下；
• （4）此时 q 指向的就是要删除节点的前一个节点（n-1处），删除第 n 个节点；

3）时间复杂度

        双指针遍历时间复杂度为 $O(n)$

---

习题2：LeetCode 876 链表的中间节点

1）题目链接

原题链接： 链表的中间节点（点击链接直达）

2） 算法思路

• 模拟枚举。奇数个节点， q 走到中点时，p->next为NULL。偶数个节点，q 走到中点时，fast为空 NULL。

3）源码剖析

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto p = head, q = head;

        while (p && p->next) {  // 只要p和p->next都不为空时，两指针就一种往后走
            p = p->next->next;
            q = q->next;
        }
        return q;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

3）时间复杂度

        双指针遍历时间复杂度为 $O(n)$

---

习题3：LeetCode 160 相交链表

1）题目链接

原题链接： 相交链表（点击链接直达）

2） 算法思路

• 判断相交：两指针是否相等；
• 难点：两个链表相同节点前面的长度不同，无法控制遍历的长度。
  例如，链表 a： 1=>2=>3=>4，链表 b：5=>3=>4，相同节点为 3。对于3 前面的链表部分，两个链表长度不同；
• 解决：将两个链表逻辑上拼接在一起。先遍历链表 a，遍历完后再遍历链表 b。同理，先先遍历链表 b，遍历完后再遍历链表 a。这样，相同节点前面的长度就保持一致了，可以通过遍历相同的次数走到相同的节点；
  例如，链表 a 逻辑上变为：1=>2=>3=>4=>5=>3=>4，链表 b 逻辑上变为：5=>3=>4=>1=>2=>3=>4；

3）源码剖析

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
        	// p没走到A链表终点就一直往后走，走到终点就开始走B链表
            p = p != NULL? p->next : headB;
            // q没走到B链表终点就一直往后走，走到终点就开始走A链表
            q = q != NULL? q->next : headA;
        }
        return p;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3）时间复杂度

         $O(n)$

---

习题4：LeetCode 141 环型链表

1）题目链接

原题链接： 环型链表（点击链接直达）

2） 算法思路

• 明确什么叫有环；
• 明确有环和无环的区别：
  • 定义：fast 是跑得快的指针，slow是跑的慢的指针。快指针每次走两步，慢指针每次走一步；
  • 有环：有环相当于 fast 和 slow 两指针在环形操场跑，如果 fast 和 slow 相遇，那一定是 fast 超过了 slow 一圈；
  • 无环：无环相当于 fast 和 slow 两指针在直道操场跑，因为快指针跑的快会先达到终点，则两指针一定不会遇到；

3）源码剖析

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;

        while (fast && fast->next)			//（1）
        {
            fast = fast->next->next;		//（2）
            slow = slow->next;				//（3）
            if (fast == slow) return true;	//（4）
        }
        return false;						//（5）
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• （1）判断快指针是否到达终点；
• （2）快指针每次走两步；
• （3）慢指针每次走一步；
• （4）两指针相遇，证明两指针套圈了，则一定有环；
• （5）快指针先达到终点，证明无环；

4）时间复杂度

         $O(n)$

---

习题5：LeetCode 142. 环形链表 II

1）题目链接

原题链接： 环形链表 II（点击链接直达）

2） 算法思路

• 本题在上题的基础上增加了新需求。除了判断是否有环，还需要返回入环节点的索引；
• 定义两个指针，一个是 fast，一个是 slow， fast一次走两步，slow一次走一步；
• 先让两指针相遇
  • fast指针走过的路程：$a+b+n\times 圈$，$圈=b+c$，得出 $a+b+n(b+c)$；
  • slow指针走过的路程 $a+b$；
  • 根据时间相等： $a+b$ = $(a+b+n\times (b+c))/2$      公式①；
• 相遇后找入口节点
  • 当两指针相遇之后，一个指针从头结点 head出发，另一个指针从相遇点出发，两指针以相同速度走，直到相遇为止，相遇的点就是链表环的入口节点；
  • 将公式① 等式两边消掉一个 $a+b$，得到 $a+b$ = $n × (b + c)) ，得到 $a$ = $n\times (b+c)-b$，因为是环形的，$a$ = $(n-1)\times (b+c)+c$；

• 图注：| 表示入环节点的位置，a 表示从起点出发到入环节点位置的路程，b 表示从入环节点的位置到相遇节点位置的路程，c 表示从相遇节点位置到入环节点位置的路程，* 表示两指针相遇节点的位置

3）源码剖析

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return NULL;

        ListNode* slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                ListNode* cur = head;
                while (cur != slow)
                {
                    cur = cur->next;
                    slow = slow->next;
                }
                return cur;
            }
        }
        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

4）时间复杂度

         $O(n)$

---

习题6：LeetCode 234 回文链表

1）题目链接

原题链接： 回文链表（点击链接直达）

2） 算法思路

• 链表不能向数组一样直接通过索引找到链表的中点，需要从头节点挨个遍历；
• 找链表的中点（参考习题2，“LeetCode 876 链表的中间节点” 的讲解），找中点遍历时，同时将中点的前半段进行翻转
• 链表长度分奇数和偶数，如果 fast 指针没有指向 null，说明链表长度为奇数，slow 还要再向前一步；
• 再依次遍历这中点两边的两段链表，依次对比是否相同；

3）源码剖析

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head, *fast = head;
        ListNode* pre = nullptr;

        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            ListNode* next = slow->next;
            slow->next = pre;;
            pre = slow;
            slow = next;
        }
        if (fast != nullptr) slow = slow->next;  // 如果fast没有指向null，说明链表长度为奇数，slow还要再往前走一步
        while (pre && slow)
        {
            if (pre->val != slow->val) return false;
            pre = pre->next;
            slow = slow->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4）时间复杂度

         $O(n)$

---

习题7：LeetCode 21 合并两个有序链表

1）题目链接

原题链接： 合并两个有序链表（点击链接直达）

2） 算法思路

二路归并

3）源码剖析

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        auto p = list1, q = list2;
        auto dummy = new ListNode(-1);
        auto cur = dummy;

        while (p && q)
        {
            if (p->val <= q->val) 
            {
                cur->next = p;
                p = p->next;
                cur = cur->next;
            }
            else
            {
                cur->next = q;
                q = q->next;
                cur = cur->next;
            }
        }
        if (p) cur->next = p;
        if (q) cur->next = q;

        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
28

4）时间复杂度

         $O(n)$