目录

        一、链表中倒数第k个结点

            1、题目说明

            2、题目解析

        二、合并两个有序链表

            1、题目说明

            2、题目解析

        三、CM11 链表分割

            1、题目说明

            2、题目解析

---

一、链表中倒数第k个结点

 1、题目说明

题目链接：链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

示例1：

输入：1，{1,2,3,4,5}

返回值：{5} 

 2、题目解析

思路：这道题同样使用快慢指针来解决问题，快指针fast先走k步，此时，fast和slow之间就相差了k，当fast走到NULL时，slow刚好到倒数第k个位置。

注意：当k大于链表的长度时，fast先走k步，fast直接就为空了，所以返回NULL。

 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{struct ListNode* slow, * fast;slow = fast = pListHead;//fast先走k步while (k--){//链表可能没有k步长if (fast == NULL)return NULL;fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow;
}

二、合并两个有序链表

 1、题目说明

题目链接：合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 2、题目解析

思路：将两个链表的元素做对比，哪个较小哪个就下来尾插新链表，当 tail 为NULL 时，需要将list1 or list2赋值给它，再者需要注意当其中一个链表比较完了，另外一个有剩余的时候，需要将它剩余链表赋给tail。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode* head, * tail;head = tail = NULL;//取小的尾插while (list1 && list2){if (list1->val < list2->val){if (tail == NULL){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;return head;
}

三、CM11 链表分割

 1、题目说明

题目链接：CM11 链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

 2、题目解析

思路：整体的逻辑就是再创建两个链表，其中一个存储原链表中比 x 小的节点元素。另外一个新的链表存储原链表中比 x 大的元素。但是题目中还有一个条件，就是保持原链表中节点之间的相对位置不变。因此，我们需要采用尾插的逻辑去处理。

注意：我们需要考虑一种情况，如果原先的链表最后一个节点小于x时，如下图，7链接的下一个节点为4，所以在大于x元素链表的最后，一定要进行置NULL。如果不置NULL，这个链表就是循环链表。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) 
{struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessTail->next = greaterTail->next = NULL;struct ListNode* cur = pHead;while (cur){if (cur->val < x){lessTail->next = cur;lessTail = lessTail->next;}else{greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}lessTail->next = greaterHead->next;greaterTail->next = NULL;pHead = lessHead->next;free(lessHead);free(greaterHead);return pHead;}
};

---

本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。 

   老铁们，记着点赞加关注!!!