文章目录
👻内容专栏：《LeetCode刷题专栏》
🐨本文概括：归纳链表部分经典题型。
206.反转链表、876.链表的中间节点、21.合并两个有序链表、160.相交链表、141.环形链表、142.环形链表Ⅱ🐼本文作者：花 碟
🐸发布时间：2023.5.17
1.反转链表
👉 206.反转链表
题目描述：给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例2：
输入：head = [1,2] 输出：[2,1]
👉思想1：
对链表进行遍历，改变每个节点的
next指针指向，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头节点。时间复杂度为O(N)，空间复杂度为O(1)
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //1.反转链表 改变next指针指向 struct ListNode* reverseList(struct ListNode* head){ //链表为空 if(head == NULL) return NULL; struct ListNode* prev = NULL; struct ListNode* cur = head; struct ListNode* Next = head->next; //当cur等于空结束 while(cur) { //反转 cur->next = prev; //迭代 prev = cur; cur = Next; if(Next) Next = Next->next; } return prev; }
👉思想2：
新建一个rhead节点，使用cur迭代链表，对于每个cur节点从rhead开始插入，每次插入之后，需要更新rhead，最后得到的新链表即为反转之后的链表，由于每每插入一个节点之后，需要继续在原链表进行往后迭代走，所以再定义一个
Next指针进行临时存储，头插完后给到cur。
👉图解：
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //2.头插法 struct ListNode* reverseList(struct ListNode* head){ struct ListNode* rhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* Next = cur->next; //头插 cur->next = rhead; rhead = cur; //迭代 cur = Next; } return rhead; }
2.链表的中间节点
题目描述： 给你单链表的头结点
head，请你找出并返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。
示例1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3
示例2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
👉思想：
求链表的中间节点，我们定义两个指针
slow和fast，核心思想是让slow一次走一步，fast一次走两步，但是这里有两种情况需要分别看待，1️⃣如果有一个中间节点，即链表长度为奇数，那么fast->next为空即为结束条件，2️⃣如果有两个中间节点，即链表长度为偶数，那么fast为空即为结束条件最后返回
slow，就是链表的中间节点
👉图解：
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head ,* slow = head; while(fast && fast->next) { //fast一次走两步 //slow一次走一步 fast = fast->next->next; slow = slow->next; } return slow; }
3.合并两个有序链表
题目描述： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例2：
输入：l1 = [], l2 = [] 输出：[]
示例3：
输入：l1 = [], l2 = [0] 输出：[0]
👉思想：
⚠️注意此题的提示是链表1和链表2均按非递减的顺序排列。
我们可以拿示例1的图片来看，首先还是新开辟链表头节点
head（此时说的是不带哨兵位的头节点，需要多加一个head为空的判断的情况），为了避免head会被修改，我们定义一个tail，让tail进行迭代，然后对链表l1和链表l2中的val值进行比较，值较小的进行尾插，直到有一个链表走向了空，循环就结束，但是如果另外一个链表非空，直接将tail->next指向非空链表的头节点即可。最后返回head⚠️注意还需要单独考虑
list1和list2为空的情况
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* head = NULL,* tail = NULL; //链表为空 if(list1 == NULL) return list2; if(list2 == NULL) return list1; //一个链表走向空，循环就结束 while(list1 && list2) { if(list1->val > list2->val) { if(tail == NULL) { head = tail = list2; }else { tail->next = list2; tail = tail->next; } list2 = list2->next; } else { if(tail == NULL) { head = tail = list1; }else { tail->next = list1; tail = tail->next; } list1 = list1->next; } } //另外一个链表非空，将非空链表头节点给到尾指针 if(list1) tail->next = list1; if(list2) tail->next = list2; return head; }
4.相交链表
题目描述：
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
📌题目提示：
示例1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。 换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
👉思想：
我们还是需要遍历整个链表，1️⃣需要先进行判断链表是否存在相交节点，那么如何判断两个链表是否是存在相交节点的情况呢？其实很简单，观察下方图解，表示相交的就是第一种和第二种情况，第三种情况是不可能出现的，以及上面的
示例3，所以我们只需要判断两个链表最后的尾结点是否相同，如果不相同，就说明不存在相交节点，则返回NULL，同时计算两个链表的长度（节点的数量），2️⃣我们需要定义一个longlist表示较长的链表，定义shortlist表示较短的链表3️⃣让长度长的longlist链表先迭代走，直到走到和另一个链表的长度相匹配，然后同时往后迭代移动，两个链表地址相等时，循环结束，最后返回任意一个链表地址即可。时间复杂度：O(N)，空间复杂度：O(1)
👉图解：
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* tailA = headA; struct ListNode* tailB = headB; int lenA = 1,lenB = 1; //计算两个链表节点的数量 while(tailA->next) { tailA = tailA->next; lenA++; } // while(tailB->next) { tailB = tailB->next; lenB++; } //尾结点不相等 链表不存在相交节点，此时返回NULL if(tailA != tailB) { return NULL; } //假设A链表比B链表长 struct ListNode* longList = headA; struct ListNode* shortList = headB; int gap = abs(lenA - lenB); //否则交换 if(lenA < lenB) { longList = headB; shortList = headA; } //长度大的先走 while(gap--) { longList = longList->next; } //数量相等后 同时往后走 while(longList != shortList) { longList = longList->next; shortList = shortList->next; } //两个地址相等返回任意地址 return longList; }
5.环形链表
题目描述：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回
true。 否则，返回false
示例1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
👉思想：
快慢指针解法，快指针步数为慢指针步数的两倍，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，
如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
这种思路还是模棱两可的小伙伴，可以拿笔在纸上画一画~也许能领悟到了。
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode * slow = head,* fast = head; while(fast && fast->next) { //慢指针每次走一步 //快指针每次走两步 slow = slow->next; fast = fast->next->next; //快慢指针相遇即链表带环 if(slow == fast) return true; } //链表不带环 return false; }
📌【扩展问题】为什么慢指针每次走1步，快指针每次走2步可以相遇？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
那么慢指针每次走1步，快指针每次走3、4、5……n步行吗？
假设快指针每次走3步，慢指针每次走1步，此时快指针先进入环，慢指针后进入环。假设慢指针进入环的时候，快指针的位置如图所示，
此时按照上述步骤来回是一个绕环运动，快指针每次走3步，慢指针每次走1步，它俩是永远不会相遇的，快指针刚好将慢指针套圈了，因此不一定可行。
那么快指针走其他步数呢？答案都是不一定！
🔖推论：fast会先进环，slow会后进环，假设slow进环时，fast与slow之间的距离为N，slow进环之后，fast开始追寻slow，slow每次走1步，fast每次走3步，他们之间的距离缩小2。
如果他们之间的距离N为偶数，那么下次距离为N - 2、N - 4、…… 6、4、2、0，他们可以相遇，但距离N如果为奇数，那么下次距离为N - 2、N - 4、……5、3、1、-1，他们可能会错过。故：只有快指针每次走2步，慢指针每次走1步才行的通，因为环的最小长度是1，尽可能的让他们之间的步数间距保持为1，即使套圈了，下次也能够相遇。
接下里我们继续来一道相关的变形题👇😇
6.环形链表Ⅱ
题目描述：给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅>仅是为了标识链表的实际情况。不允许修改 链表。
示例1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
👉思想：
一个指针从相遇点开始走，一个指针从链表头开始走，他们相遇时，即为入环的第一个节点。
👉 代码实现：
* Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * fast = head; struct ListNode * slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { //求环的入口点 struct ListNode * meet = slow; while(head != meet) { head = head->next; meet = meet->next; } return meet; } } //链表无环 return NULL; }
🔖推理：
这种思想没看懂？我们不妨花五分钟来推理一下：
fast走的路程是slow的2倍。我们假设链表头
head到环的入口点的距离为L，假设环的入口点到相遇点meet(即fast第一次追寻上slow)的距离为X，假设环的长度为C，所以我们可以得出slow走的路程为L+X，fast走的路程为L + n*C + X，n为slow在入环前，fast转过环的圈数，也就是说n的大小取决于L和C的长度，n的范围一定是≥1的。所以我们可以列出一个式子：2(L+X) = L + n*C + X，即
L = n*C - X或者看成L = (n- 1)*C + C - X这里的n*C就是相遇点，减去X后就是入环口，而head走过的L距离之后也正好是入环口，这就应证了我们开始的思想。
👉图解：
👉思想2：
定义一个
meetNext指针，用来保存相遇点的next，并将meet->next置为NULL。从meetNext开始，与头节点head开始一起遍历，此时可以转换为链表相交问题，相交节点即为环的入口点。
👉 代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* tailA = headA; struct ListNode* tailB = headB; int lenA = 1,lenB = 1; //计算两个链表节点的数量 while(tailA->next) { tailA = tailA->next; lenA++; } // while(tailB->next) { tailB = tailB->next; lenB++; } //尾结点不相等 链表不存在相交节点，此时返回NULL if(tailA != tailB) { return NULL; } //假设A链表比B链表长 struct ListNode* longList = headA; struct ListNode* shortList = headB; int gap = abs(lenA - lenB); //否则交换 if(lenA < lenB) { longList = headB; shortList = headA; } //长度大的先走 while(gap--) { longList = longList->next; } //数量相等后 同时往后走 while(longList != shortList) { longList = longList->next; shortList = shortList->next; } //两个地址相等返回任意地址 return longList; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * fast = head; struct ListNode * slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { //求环的入口点 struct ListNode* meet = slow; struct ListNode* meetNext = meet->next; meet->next = NULL; //转换为链表相交问题 struct ListNode* pos = getIntersectionNode(head,meetNext); return pos; } } //链表无环 return NULL; }
链表部分题型就到这里，如果对小伙伴们有帮助的话，还请三连支持支持我哦😉😉
