链表中倒数第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 ListNostruct 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; } de* list2){
当然这种涉及遍历的题目十有八九都可以用递归解决：
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; } };
