冰冰学习笔记:这些链表练习题,你会吗?(中)
欢迎各位大佬光临本文章!!!
还请各位大佬提出宝贵的意见,如发现文章错误请联系冰冰,冰冰一定会虚心接受,及时改正。
本系列文章为冰冰学习编程的学习笔记,如果对您也有帮助,还请各位大佬、帅哥、美女点点支持,您的每一分关心都是我坚持的动力。
我的博客地址:bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog
我的gitee:冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool
系列文章推荐
冰冰学习笔记:这些链表练习题,你会吗?(上)
目录
系列文章推荐
前言
1.链表中倒数第K个结点
(1)暴力求解
(2)快慢指针变体形式,先走k步
2.合并两个有序链表
3.链表分割
4.链表相交
5.环形链表
6.链表的回文结构
前言
前面的一篇文章我们主要讲解了链表习题中的双指针思想,例如快慢指针,今天我们还要学一下其他的解题思想。正如杭哥所言,第一难的是找到解决问题的思路,然后是解决方案是否能普世运用,适应各种极端场景。下面我们接着盘那些链表题。
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 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 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; }};
未完待续!!!