单手杀穿经典链表题Pt.2——LeetCode天梯渡劫（倒数第k节点，合并链表，链表分割，回文结构）_综合

传统艺能?

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（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;}
};

这三段式下来还不轻轻松松把他干的稀碎？怎么样你学废了吗？
在这里插入图片描述

今天就到这里，摸了家人们。

单手杀穿经典链表题Pt.2——LeetCode天梯渡劫（倒数第k节点，合并链表，链表分割，回文结构）

目录

传统艺能?

链表中倒数第k个结点?

合并两个有序链表?

CM11 链表分割?

链表的回文结构?