05

#05 | 来源: 网络整理| 查看: 265

前言

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

文章目录前言一. 基础回顾二. 高频考题1、例题例题1：LeetCode 206 反转链表1）题目链接2）算法思路3）源码剖析4）时间复杂度例题2：LeetCode 92 反转链表II1）题目链接2）算法思路3）源码剖析4）时间复杂度例题3：LeetCode 203 移除链表元素1）题目链接2）遍历做法3）递归做法3）时间复杂度2、习题习题1：LeetCode 19 删除链表的第N个节点1）题目链接2）算法思路3）源码剖析3）时间复杂度习题2：LeetCode 876 链表的中间节点1）题目链接2）算法思路3）源码剖析3）时间复杂度习题3：LeetCode 160 相交链表1）题目链接2）算法思路3）源码剖析3）时间复杂度习题4：LeetCode 141 环型链表1）题目链接2）算法思路3）源码剖析4）时间复杂度习题5：LeetCode 142. 环形链表 II1）题目链接2）算法思路3）源码剖析4）时间复杂度习题6：LeetCode 234 回文链表1）题目链接2）算法思路3）源码剖析4）时间复杂度

一. 基础回顾

参考上一讲： 04 |「链表」简析

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

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

虚拟头结点（dummy）：针对链表，需要经常判断头结点（head）头结点为空和不为空对应不同的操作，增加哨兵节点统一操作。如果链表为空(head = null)，那么访问 null.val 与 null.next 出错。为了避免这种情况，增加一个虚拟头结点（dummy），其中 dummy 的值（val）常用 -1 表示，这样 dummy.next = null，避免直接访问空指针。

// 增加虚拟头节点的链表遍历 dummy; dumm->next = head; p = dummy; while (p) {} // 没有虚拟头结点的链表遍历 head; while (head) {head = head->next; } 二. 高频考题 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）：初始化变量 last 和 cur， last 指向上一个节点，cur 指向当前节点；（3）：修改每条边，需要循环遍历访问每个节点；（4）：修改一条边时，先保存当前节点（cur）的下一个节点（next），防止丢失；（5）：修改一条边；（6）/（7）：last 和 cur 分别向后移动一位；（8）：返回反转后链表的头结点。当 cur 停下时指向原链表的 NULL，此时 last 指向反转后链表的头结点； 4）时间复杂度

O(n)O(n)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）：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)O(n)O(n)

例题3：LeetCode 203 移除链表元素 1）题目链接

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

2）遍历做法增加 dummy 哨兵节点的目的是统一操作，少写特判断头结点（head）是否为空。// 不增加哨兵节点dummy if (!head) {return head; } else {} // 增加哨兵节点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;} }; 3）递归做法 if (!head) return head; head->next = removeElements(head->next, val); return head->val == val? head->next : head; 3）时间复杂度

O(n)O(n)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）：定义虚拟头结点 dummy，不用考虑头结点的特殊情况；（2）：p 指针先走 n 步；（3）：p 指针和 q 指针同时走，直到 p 指针走到最后一个节点，两指针都停下；（4）：此时 q 指向的就是要删除节点的前一个节点（n-1处），删除第 n 个节点； 3）时间复杂度

双指针遍历时间复杂度为 O(n)O(n)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;} }; 3）时间复杂度

双指针遍历时间复杂度为 O(n)O(n)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;} }; 3）时间复杂度

O(n)O(n)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）：快指针先达到终点，证明无环； 4）时间复杂度

O(n)O(n)O(n)

习题5：LeetCode 142. 环形链表 II 1）题目链接

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

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

O(n)O(n)O(n)

习题6：LeetCode 234 回文链表 1）题目链接

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

2）算法思路链表不能向数组一样直接通过索引找到链表的中点，需要从头节点挨个遍历；找链表的中点（参考习题2，“LeetCode 876 链表的中间节点” 的讲解），找中点遍历时，同时将中点的前半段进行翻转链表长度分奇数和偶数，如果 fast 指针没有指向 null，说明链表长度为奇数，slow 还要再向前一步；再依次遍历这中点两边的两段链表，依次对比是否相同； 3）源码剖析 class Solution { public:bool isPalindrome(ListNode* head) {auto slow = head, fast = head;ListNode* pre = NULL;while (fast && fast->next){fast = fast->next->next;auto next = slow->next;slow->next = pre;pre = slow;slow = next; }if (fast) slow = slow->next;while (pre && slow){if (slow->val != pre->val) return false;pre = pre->next;slow = slow->next;}return true;} }; 4）时间复杂度

O(n)O(n)O(n)

【本文地址】

05

05

今日新闻

推荐新闻