欢迎各位大佬光临本文章!!!
还请各位大佬提出宝贵的意见,如发现文章错误请联系冰冰,冰冰一定会虚心接受,及时改正。
本系列文章为冰冰学习编程的学习笔记,如果对您也有帮助,还请各位大佬、帅哥、美女点点支持,您的每一分关心都是我坚持的动力。
我的博客地址:bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog
我的gitee:冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool
系列文章推荐
冰冰学习笔记:这些链表练习题,你会吗?(上)
前言
前面的一篇文章我们主要讲解了链表习题中的双指针思想,例如快慢指针,今天我们还要学一下其他的解题思想。正如杭哥所言,第一难的是找到解决问题的思路,然后是解决方案是否能普世运用,适应各种极端场景。下面我们接着盘那些链表题。
1.链表中倒数第K个结点
题目链接:链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
题目描述:输入一个链表,输出该链表中倒数第k个结点。
该题目的意思就是接收两个参数,一个参数为K,代表返回数组的结点位置,另一个参数为链表。
例如,链表:1,2,3,4,5。K为2,则返回链表中的倒数第2个结点,即返回存储元素4的链表地址,输出即为4,5。
(1)暴力求解
暴力求解的方法是我们最先想到的方法,这也是我们的底线,当我们想不到其他更好的方法的时候,自己也能解决这道题目。
暴力求解就是我先遍历链表找到链表结点个数count,然后pos=count-k得到需要倒数第k个结点与头节点相差的步数,然后通过循环走到pos的位置,返回该节点的地址即可。
但是这个题还要注意一些特殊情况。
情况一:链表为NULL,链表是空链表,没有元素,怎么返回呢?返回NULL指针。
情况二:K过大,K大于元素个数count,无法返回,此时应该返回NULL指针。
情况三:K为0,返回倒数第0个结点?应该返回NULL指针。
剩下的情况才是我们一开始分析的状况。
全部考虑之后开始写代码:
先考虑情况一和情况三,这两个直接用if语句进行排查即可。由于在普通情况下我们需要得到count的大小 ,那时在判断第二种情况。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* cur = pListHead;
//排查链表是否为空
if ( cur == NULL )
{
return cur;
}
//排查k是否为0
else if ( k == 0 )
{
return NULL;
}
//普通情况
else
{
int count = 0;
while ( cur != NULL )
{
cur = cur->next;
count++;
}
//排查k是否大于链表长度
if ( k > count )
{
return NULL;
}
int pos = count - k;
cur = pListHead;
while ( pos )
{
cur = cur->next;
pos--;
}
return cur;
}
我们发现此种方式写完代码后,我们对代码遍历了两遍,能否遍历一遍就找到呢?答案是可以的,我们来看第二种解法。
(2)快慢指针变体形式,先走k步
这种方式也是快慢指针的形式,创建两个指针,一个指针先走k步,然后两个指针一起走,当先走的快指针走到链表最后的时候,慢指针则走到了倒数第k个结点的位置,然后返回慢指针指向的地址即为所求。此时会发现,我们对链表仅仅遍历了一遍就解决了问题。
当然,前面所讲的特殊情况我们也得考虑进去,在考虑情况二的时候我们放在fast指针先走k步的时候,如果循环还没跳出,fast已经指向NULL了,则说明k的长度是大于整体长度,直接返回NULL。
因此代码如下:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* fast = pListHead;
struct ListNode* slow = pListHead;
//排查链表是否为空以及k是否为0
if ( slow == NULL || k==0)
{
return NULL;
}
else
{
while ( k-- )
{
//排查k是否大于链表长度
if ( fast == NULL )
{
return NULL;
}
fast = fast->next;
}
while ( fast != NULL )
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
2.合并两个有序链表
题目链接:21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
该题目和我们以前做的合并两个有序数组的题目类似,只不过此时合并的是链表。例如,链表A:1,3,5,7,9。链表B:2,4,6,8。将两个链表合并之后得到新链表:1,2,3,4,5,6,7,8,9。
在这里我们使用的思想就是归并,即从头开始比较两个链表,取较小值尾插到新链表中。当任一方指向NULL时结束循环,然后判断二者是否为空,将不为空的直接链接在新链表后方,由于本身就为有序链表,因此连接后一定是有序的链表。
分析过后,代码如下所示:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* n1 = list1;
struct ListNode* n2 = list2;
struct ListNode* tail = NULL;
struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
newnode->next = NULL;
tail = newnode;
while ( n1 && n2 )
{
if ( n1->val <= n2->val )
{
tail->next = n1;
n1 = n1->next;
tail = tail->next;
}
else
{
tail->next = n2;
n2 = n2->next;
tail = tail->next;
}
}
//连接剩余元素
if ( n1 )
{
tail->next = n1;
}
else
{
tail->next = n2;
}
struct ListNode* tmp = newnode;
newnode = tmp->next;
free(tmp);
return newnode;
}
由于我们创建了头节点,因此不用去单独考虑链表有空的情况。我们创建tail指针保存每次尾插后的地址,方便我们下一次尾插。切记最后一定要释放开辟的头结点,避免照成内存泄漏。
值得注意的是,我们的连接剩余元素不需要像数组那样一个元素一个元素的连接,只需要一步连接即可。
3.链表分割
题目链接:链表分割_牛客题霸_牛客网 (nowcoder.com)
题目描述:现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
什么意思呢?简单来说就是将一个链表分成两部分,一部分小于x一部分x。例如链表A:1,3,6,5,2,8。给定分割值x为4,那么链表就被分割成1,3,2和6,5,8两个部分,最终链表将变为1,3,2,6,5,8。但是相对顺序并没有改变,6本来就在5的前面,分割完还是在前面。只是将小于4的放在链表前面,大于等于4的放在了链表后面。
那么这个题怎么做呢?其实题目就给了我们提示,题目告知我们更改后链表前面是小于x的,后面是大于等于x的。那么我们就可以将链表分成两部分进行操作,遍历链表,将链表中小于x的结点尾插一个新链表,大于等于x的结点尾插一个新链表。
在cur指向NULL之后循环停止,最终将得到两个新链表:
1,3,2和6,5,8。
然后我们将head1的末尾与head2的开头相连接,则得到我们重新排序的链表。
这样就结束了吗?
我们看下面这种情况,当链表元素为1,3,8,5,6,2 的时候,通过我们上述的方法将会变成两个链表:1,3,2和8,5,6。然后将其链接到一起,结果却跑不过去。
为什么呢?
因为我们分割完后,head2中最后一个元素为6,6所在结点指向2所在的结点,无意之中链表形成了一个环。
所以我们要注意:在循环停止后,先对head2的尾部进行处理,再连接到一起,形成一整个链表。
代码如下:
struct ListNode* partition(struct ListNode* pHead, int x)
{
// 判断是否为空链表
if ( pHead == NULL )
{
return pHead;
}
struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail1 = head1;
struct ListNode* tail2 = head2;
head1->next = NULL;
head2->next = NULL;
struct ListNode *cur = pHead;
//尾插链表
while ( cur != NULL )
{
if ( cur->val < x )
{
tail1->next = cur;
tail1 = tail1->next;
}
else//依据题意不用单独考虑相等情况
{
tail2->next = cur;
tail2 = tail2->next;
}
cur = cur->next;
}
tail1->next = head2->next;
//将大的一端尾部置空,避免形成环状
tail2->next = NULL;
struct ListNode* tmp = head1->next;
free(head1);
free(head2);
return tmp;
}
4.链表相交
题目链接:160. 相交链表 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你两个单链表的头节点
headA
和
headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 NULL。
我们可以将题目分解为两部分进行理解,首先判断链表是否相交,如何判断链表是否相交呢?
我们知道,如果两个链表相交,那么链表的后面一定是相同的,相交的链表不会是交叉型的,因为next只能指向一个结点。
那怎么判断链表相交呢?很简单,既然相交的链表后面是相同的,那我们直接遍历链表,找到两个链表的最后一个结点,判断结点的地址是否相同,如果相同则说明链表相交,如果不同则不相交。
然后我们在寻找链表的第一个相交的结点。我们最先想到的就是将两个链表的每个结点都进行一一比较,找到第一次相同的地址即可,但是,这种算法的复杂度是有可能达到O(N^2)的,不可取。
下面我们介绍一个O(N)的算法。
首先我们先找到List1和List2的长度len1,len2。然后求得两长度的差值gap,再让长的链表先走差值gap步 ,然后两个链表在一起遍历,逐个地址进行比较,第一次相同的即为第一个交点。
具体过程如下所示:
当然,链表为空的情况我们需要提前判断。
具体代码如下:
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
if ( headA == NULL || headB == NULL )
{
return NULL;
}
struct ListNode* curA = headA;
struct ListNode* curB = headB;
int lenA = 1, lenB = 1;
//找尾结点并计算链表长度
while ( curA->next != NULL )
{
curA = curA->next;
lenA++;
}
while ( curB->next != NULL )
{
curB = curB->next;
lenB++;
}
//判断尾结点是否相同,相同则为有交点
if ( curA != curB )
{
return NULL;
}
//判断长短
struct ListNode* shortlen = headA;
struct ListNode* longlen = headB;
if ( lenA > lenB )
{
shortlen = headB;
longlen = headA;
}
int gap = abs(lenA - lenB);
//让长的先走差值步
while ( gap-- )
{
longlen = longlen->next;
}
//找第一个交点
while ( longlen != shortlen )
{
longlen = longlen->next;
shortlen = shortlen->next;
}
return shortlen;
}
代码中我们在寻找尾结点的同时计算出了链表长度,由于我们寻找的是尾结点,而并非NULL,所以判定条件为cur->next不为NULL才进入循环内部,但是这样求的长度会比原链表少1。所以我们在定义len的时候直接将其初始化为1。
判断长短我们没有直接使用len的长度来判断,而是新定义两个变量shortlen和longlen进行后续的操作,使代码会变的更加易读。
5.环形链表
题目链接:141. 环形链表 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个链表的头节点
head
,判断链表中是否有环。
看着题目描述很简单,就是去判断链表有没有环,简单我们只需要记录一下结点就行了,然后遍历链表,当指针再次回到记录的点时就证明链表有环。可以是可以,但是我们要记录的结点就多了,时间复杂度也会很大。
此时还会有人说,简单啊,有环的链表没有NULL,没环的有NULL,判断哪个有NULL不久完了!
额,没环的确实遇到NULL循环停下来了,有环的怎么停呢?这步死循环了吗?出不来呀,难不成程序崩溃了就证明他有环?这肯定不行。那有没有其他的办法呢?
有,采用快慢指针。
什么意思呢?我们设定两个指针,慢指针slow每次走一步,快指针fast每次走两步。循环条件就是fast以及fast->next不为NULL,如果遇到NULL则说明链表不为环状,跳出循环,返回false。
如果存在环状,则两个指针最终都会进入环状中,这时就演变为一个追及问题,快指针将会在若干步数后追到慢指针,然后两个指针相遇,返回ture。
具体过程如下:
代码其实很简单就是在快慢指针基础上加上判断即可。
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head,*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return true;
}
}
return false;
}
6.链表的回文结构
题目链接:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述:
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
什么是回文结构,就是判断这个链表是否对称。例如一个链表1,2,3,2,1。链表对称是回文结构,链表,1,2,3,3,2。链表不对称,不是回文结构。
那怎么判断呢?有的人会将链表的val拷贝到数组中,然后利用双指针判断,但是我们需要额外开辟空间来存放这n个元素,所以便超过了空间复杂度O(1)。
所以我们想到了这样一个解法,先找到链表的中间结点,然后反转后半部分链表,最后一一对比。
反转链表以及寻找中间结点的办法我们之前都讲过了,此时直接拿来复用即可。
我们要注意什么时候停止比较?当指向链表开头的指针与指向链表中间的指针遍历都指向NULL的时候就停止遍历比较。后半部分好理解,反转后一定有指向NULL的结点,那前半部分呢?
我们发现,前半部分没有变化,中间结点的前一个结点的next还是指向中间结点的地址,即便原来的中间结点经过逆置已经到最后一个结点了。
那我们就好判断了,因为无论链表是奇数个结点还是偶数个结点都不会影响结果了,奇数个结点的中间结点都会被遍历判断不影响结果。
具体过程:
代码如下:
class PalindromeList
{
public:
//找链表的中间结点
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow;
struct ListNode* flast;
slow = flast = head;
while ( flast && flast->next )
{
slow = slow->next;
flast = flast->next->next;
}
return slow;
}
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{
if ( head == NULL )
{
return head;
}
struct ListNode* tmp = NULL;
struct ListNode* pre = head;
struct ListNode* cur = head->next;
while ( pre != NULL )
{
pre->next = tmp;
tmp = pre;
pre = cur;
if ( cur != NULL )
cur = cur->next;
}
return tmp;
}
//判断是否为回文结构
bool chkPalindrome(ListNode* A)
{
// write code here
struct ListNode* head = A;
struct ListNode* mid = middleNode(head);
struct ListNode* newhead = reverseList(mid);
while ( head && newhead )
{
if ( head->val != newhead->val )
{
return false;
}
else
{
head = head->next;
newhead = newhead->next;
}
}
return true;
}
};
未完待续!!!
版权归原作者 bingbing~bang 所有, 如有侵权,请联系我们删除。