单手杀穿经典链表题Pt.2——LeetCode天梯渡劫
目录
传统艺能😎
小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库（打灰人 ）欢迎访问，点我！
🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我
既然选择了远方，便只顾风雨兼程！
链表中倒数第k个结点🤔
链接：链表中倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。
示例： 输入：1,{1,2,3,4,5}
返回值：{5}
思路：一提到倒数啥的，可能大家 DNA 动了，会想到：超，这还不简单，用之前的反转链表，再遍历到 k 位节点就能搞定这冤种。
当你沉迷于上面的丝滑小连招时，我的评论是可以但格局没打开，我的方法还是这位重量级：快慢指针。
我们定义出快指针先走出 k 步，再从开头定义出慢指针，同时开始走，当快指针走到尾巴上时慢指针就正好落在倒数 k 个数的头上
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast= pListHead; struct ListNode* slow= pListHead;; if(pListHead==NULL) { return NULL; } while(k--) { if(fast==NULL) { return NULL; } fast = fast->next;//fast指针先走，拉出k个身位 } while(fast) { fast = fast->next; slow = slow->next; } return slow;}你学废了吗~
合并两个有序链表🤔
链接：合并两个有序链表
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
示例 ：
输入：L1 = [1,2,3], L2 = [3,4,5]
输出：[1,2,3,3,4,5]
思路：思路很简单，就是一个一个拼接在一起，为了方便对头结点进行操作我们依然采用哨兵位头结点：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* guard = malloc(sizeof(struct ListNode)); struct ListNode* cur = guard;//初始化哨兵位头结点while(list1 && list2){ if(list1->val<=list2->val) {cur->next = list1;list1 = list1->next;cur=cur->next; } else {cur->next = list2;list2 = list2->next;cur=cur->next; }//利用有序性进行衔接} if(list1==NULL) { cur->next = list2; } if(list2==NULL) { cur->next = list1; }//处理链表为空的特殊情况return guard->next;}当然这种涉及遍历的题目十有八九都可以用递归解决：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}else if(list2==NULL){return list1;}else if(list1->val <= list2->val){list1->next = mergeTwoLists(list1->next,list2);return list1;}else {list2->next = mergeTwoLists(list1,list2->next);return list2;}}递归的方法很容易理解，但是也要注意在链接各个节点时不要改变了头节点的值。
你学废了吗~
CM11 链表分割🤔
链接：CM11 链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
这题没有示例我们其实也不需要，阅读理解能够拿捏，作图也省了（我是懒狗）
思路：这道题牛客给出的难度是较难，其实做了才知道不过如此，放在力扣可能连中等都没有。很简单，就是将大小节点从分开撇清，一半在前一半在后即可。既然如此我们就开两个空间，一个存小一个存大，最后落脚点又落在了链表合并上
注意开哨兵位节点有借有还，最后返回的一定是原链表的头节点：
class Partition {public: ListNode* partition(ListNode* pHead, int x) {struct ListNode*head1,*tail1,*head2,*tail2; head1 = tail1 =(struct ListNode*)malloc(sizeof(struct ListNode)); head2 = tail2 =(struct ListNode*)malloc(sizeof(struct ListNode)); //开辟空间，一个存大一个存小 tail1->next = NULL; tail2->next = NULL; struct ListNode*cur = pHead;//设置哨兵位节点 while(cur) { if(cur->val < x) { tail1->next = cur; tail1 = tail1->next; cur = cur->next; } else { tail2->next = cur; tail2 = tail2->next; cur = cur->next; } }tail1->next = head2->next; tail2->next = NULL; pHead = head1->next; free(head1); free(head2); return pHead;}};你学废了吗~
链表的回文结构🤔
链接：链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构；给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构，保证链表长度小于等于900
示例：
1->2->2->1
返回：true
思路：扎不多德勒，这题又是较难，我™直接就这，其实这道题称他为“一会三通”不为过分，本质缝合怪，我们要判断回文首先需要找到链表中间节点，将后半部分进行链表反转，最后再将前后两部分进行链表比较，一样则返回 true。所以都是我们之前的题，现成的拿来用即可：
class PalindromeList {public: bool chkPalindrome(ListNode* A) { if(A==NULL) return false; ListNode* slow=A,*fast=A; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; }//链表的中间节点 ListNode* cur=NULL,*next=slow; while(slow){ next=slow->next; slow->next=cur; cur=slow; slow=next; }//链表反转 next=A; while(cur){ if(next->val!=cur->val) return false; next=next->next; cur=cur->next; }//链表比较 return true; }};这三段式下来还不轻轻松松把他干的稀碎？怎么样你学废了吗？
今天就到这里，摸了家人们。
