👻内容专栏:《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)
👉 代码实现:文章来源:https://www.toymoban.com/news/detail-450814.html
/**
* 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.链表的中间节点
👉 876.链表的中间结点
题目描述: 给你单链表的头结点
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.合并两个有序链表
👉21.合并两个有序链表
题目描述: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例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.相交链表
👉160.相交链表
题目描述:
给你两个单链表的头节点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.环形链表
👉141.环形链表
题目描述:
给你一个链表的头节点 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.环形链表Ⅱ
👉142.环形链表Ⅱ
题目描述:给定一个链表的头节点
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;
}
链表部分题型就到这里,如果对小伙伴们有帮助的话,还请三连支持支持我哦😉😉文章来源地址https://www.toymoban.com/news/detail-450814.html
到了这里,关于【LeetCode】每日一题:链表部分经典题型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!