链表中倒数第K个节点

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

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

1.遍历求长度，根据k求结果

代码思路和上题十分类似，十分简单

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   
   
    // write code here
    struct ListNode* cur=pListHead;
    struct ListNode* prev=pListHead;
    int flag=0;
    while(cur)
    {
   
   
        cur=cur->next;
        flag++;
    }
    if(k>flag)
    {
   
   
        return NULL;
    }
    for(int i=0;i<flag-k;i++)
    {
   
   
        prev=prev->next;
    }
    return prev;
}

2.仿照上题，快慢指针的方法解决

和上题相比，略有不同的一点是，上面的快指针每次走的是一样的，而对于这个题来说，假设K=4，那么就令快指针每次走四格，其余思路和上题类似

总结原理：这里既然要求的是倒数第k个，那么就令fast指针和slow指针之间差k个，然后两个一起走，当fast指针到末尾的时候，slow所在的位置就是fast位置减去它们一开始的距离差，也就是倒数k个的位置

整体思路是十分巧妙的，其实原理和方法1类似，都是找到最后一个元素，然后再找前面倒数的元素，但相比起来使用快慢指针的方法可以让时间复杂度缩短到最少

==代码实现如下==

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   
   
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    for(int i=0;i<k;i++)
    {
   
   
        if(fast)
            fast=fast->next;
        else
         return NULL;
    }
    while(fast)
    {
   
   
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

这里思考
第一次走k步和走k-1步有什么区别？

链表分割问题

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

由于题目描述中提到，不能改变原来的数据顺序，那么也就意味着只能尾插，因为尾插不会破坏数据顺序

于是，我们要做的实际上就是把小于val的单独拿出来，大于等于val的单独拿出来，创建两个节点让拿出来的这两份数据分别进行尾插，最后再实现链表的合并，即可解决这个问题

代码的实现也相对简单，代码实现如下

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
   
   
public:
    ListNode* partition(ListNode* pHead, int x) {
   
   
        // write code here
        struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail;
        lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));

        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;
    }
};