快慢指针

快慢指针中的快慢指的是移动的步长，快慢分别指的是快指针每次移动两步，满指针每次移动一步

快慢指针的应用

·判断单链表是否存在环

判断是否存在环的最好方法就是让快指针和慢指针同时从头开始遍历整个链表，如果是环的话，慢指针一定会在某一时刻追上快指针，反之则不然；或者快指针到达了NULL，那么也能说明该单链表是不存在环的，代码如下：

bool isCircle(Node *p)
{
    if(head == nullptr)
        return false;
    Node *slow = head;
    Node *fast = head;
    while(fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}

这样我们就可以实现一个对单链表是否有环的判断

·在有序链表中寻找中位数

因为快指针是慢指针的二倍，因此快指针在到达终点的时候，慢指针正好指向中点的位置。

同时我们还要考虑链表结点个数的奇偶数，当快指针移动x次后到达表尾，说明链表有奇数个(2x+1)结点，直接返回慢指针指向的数据即可。
如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

具体代码如下：

while(fast && slow)
{
    if(fast->next == nullptr)
        return slow->data;
    else if(fast->next != nullptr && fast->next->next==nullptr)
        return (slow->data + slow->data)/2;
    else{
        slow = slow->next;
        fast = fast->next->next;
    }
}

·输出链表中的倒数第k个节点

可以定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第K步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时候，第二个指针正好是倒数第K个节点。

具体实现如下：

ListNode *GetNode(ListNode *p, int k)
{
    if(k == 0 || p == nullptr)
        return NULL;
    ListNode *fast = p;
    ListNode *slow = p;
    for(int i = 0; i < k-1; i++)
    {
        fast = fast->next;
        if(fast == nullptr) return NULL;
    }
    while(fast -> next != nullptr)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

这是主要的几种应用，之所以要写出这几种写法，一方面是介绍快慢指针，另一方面是提出下面的几道在leetcode上见到的题都是用快慢指针来解决问题的。

快慢指针的习题参考

143. Reorder List

首先，第一题是143. Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

我们这道题就可以借助快慢指针进行解决：
先用快慢指针将整个链表一分为二，在将第二个子链表进行倒序求解，最后合并的到最终的结果：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head ==NULL || head->next == NULL ||head->next->next == NULL)
            return;
        ListNode *fast,*slow,*head1,*head2,*post,*cur,*tmp = NULL;
        fast = slow = head;
        while(fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        head1 = head;
        head2 = cur = slow->next;
        slow->next = nullptr;
        //将第二部分链表反转
        post = head2->next;
        cur->next = NULL;
        while(post!=NULL)
        {
            tmp = post->next;
            post->next = cur;
            cur = post;
            post = tmp;
        }
        head2 = cur;
        //将第二部分插入到第一部分
        ListNode *cur1 = head1;
        ListNode *cur2 = head2;
        while(cur2!=NULL)
        {
            tmp = cur1->next;
            cur1->next = cur2;
            post = cur2->next;
            cur2->next = tmp;
            cur1 = tmp;
            cur2 = post;
        }
    }
};

第一部分就是使用的快慢指针进行的运算，通过移动指针，最后fast指针指向终点，而slow指向中点，通过这个中点，可以将整条链表分为两部分，之后就可以对这两部分进行操作了。

第二部分就是对刚才分出来的链表的后半部分进行逆转操作，比如我们原先是A->B->C的链表，我们要变成C->B->A，我们可以看出来，要发生逆转的话，顺序是发生改变的，那么意味着我们需要三个指针来进行调整，分别是当前节cur，以及前一个节点pre，和后一个节点nextnode，实现如下：

ListNode *Reverse(ListNode *p)
{
    ListNode *cur = p;
    ListNode *pre = nullptr;
    ListNode *reverseHead = nullptr;
    while(cur)
    {
        ListNode *nextnode = cur->next;
        if(nextnode == nullptr)
            reverseHead = cur;
        cur->next = pre;
        
        pre = cur;
        cur = nextnode;
    }
}

最后一部分就是实现链表的插入即可，即按照题目中的要求将两个链表一次插入即可。

234. Palindrome Linked List

第二题是234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.

Example 1:
Input: 1->2
Output: false

Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

这道题除了让判断是否为回文，还对时间复杂度和空间复杂度进行了限制，因此我们可以联想到之前所说的快慢指针将整个链表分为两部分，之后再将后面的链表进行反转，再进行比较即可。
具体步骤就不详细说明了，把代码贴出来仅供参考

    ListNode *reverseList(ListNode *head)
    {
        ListNode *pre = nullptr;
        ListNode *next = nullptr;
        while(head != nullptr)
        {
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    bool isPalindrome(ListNode* head){
        if(head == nullptr || head->next == nullptr)
            return true;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast->next != nullptr && fast->next->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = reverseList(slow->next);
        slow = slow->next;
        while(slow)
        {
            if(slow->val != head->val)
                return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }

以上就是对于快慢指针的学习