[数据结构与算法]快慢指针寻找链表中间结点

?1.?寻找链表中间结点

ps.此题出于LeetCode网。

用普通的方法不过就是开辟一个数组，将节点中的数据全部放到数组中，然后通过控制数组的下标找到处于数组中间的数据，进而找到存储相对应的数据的结点，返回结点的地址：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    int* n = (int*)malloc(sizeof(int) * 100);
    struct ListNode* cur = head;
    int i = 0;
    while (cur)
    {
        n[i] = cur->val;
        cur = cur->next;
        i++;
    }
    int tmp = 0;
    if ((i + 1) % 2 == 0)
        tmp = (i + 1) / 2 - 1;
    else
        tmp = (i + 1) / 2 ;
    cur = head;
    i = 0;
    while (i != tmp)
    {
        cur = cur->next;
        i++;
    }
    return cur;
}
//此处给出代码不再详细分析

用快慢指针分析：大致可以分为奇数个结点和偶数个结点两种情况。创建两个指针变量，一个为slow指针，一个为fast指针。slow指针一次走一步，fast指针一次走两步，走到最后fast指针走过的长度一定是slow指针走过的二倍。此时fast为最后一个结点(偶数结点时为NULL)，slow为中间的那个节点(偶数结点时为中间靠后那个节点)。最后返回slow指针即可。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next) //注意！！！
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//一定要注意while条件的写法，一定是fast在前，fast->next
//在后的因为while判断括号中的条件时是从左向右执行的，如果
//fast为NULL，那么fast->next这种写法是非法的！！

2.链表中倒数第k个结点

?这道题如果用常规的方法就是先遍历计算出n个结点，然后从头找到正数的第(n-k)个结点，再返回第n-k个结点，是比较麻烦的。但如果用双指针的方法会简单许多。

分析：创建fast和slow两个指针都指向第一个结点，先让fast走k步，然后fast和slow一起走。这样一来fast和slow之间永远相差k步，当fast走到最后时，slow正好走到倒数第K个结点。返回slow。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    
    if (pListHead != NULL)
    {
        while(k--)
        {
            if(fast == NULL)//k>n k<0的情况
                return NULL;
            fast = fast->next;
        }
        
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
    else
        return NULL;
}