快慢指針

快慢指針中的快慢指的是移動(dòng)的步長(zhǎng)矾缓，快慢分別指的是快指針每次移動(dòng)兩步稻爬，滿指針每次移動(dòng)一步

快慢指針的應(yīng)用

·判斷單鏈表是否存在環(huán)

判斷是否存在環(huán)的最好方法就是讓快指針和慢指針同時(shí)從頭開始遍歷整個(gè)鏈表桅锄，如果是環(huán)的話样眠，慢指針一定會(huì)在某一時(shí)刻追上快指針，反之則不然辫秧；或者快指針到達(dá)了NULL被丧，那么也能說明該單鏈表是不存在環(huán)的，代碼如下：

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

這樣我們就可以實(shí)現(xiàn)一個(gè)對(duì)單鏈表是否有環(huán)的判斷

·在有序鏈表中尋找中位數(shù)

因?yàn)榭熘羔樖锹羔樀亩妒辆浚虼丝熘羔樤诘竭_(dá)終點(diǎn)的時(shí)候蝇摸，慢指針正好指向中點(diǎn)的位置。

同時(shí)我們還要考慮鏈表結(jié)點(diǎn)個(gè)數(shù)的奇偶數(shù)貌夕，當(dāng)快指針移動(dòng)x次后到達(dá)表尾啡专，說明鏈表有奇數(shù)個(gè)(2x+1)結(jié)點(diǎn)，直接返回慢指針指向的數(shù)據(jù)即可辱揭。
如果快指針是倒數(shù)第二個(gè)結(jié)點(diǎn)病附，說明鏈表結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)，這時(shí)可以根據(jù)“規(guī)則”返回上中位數(shù)或下中位數(shù)或（上中位數(shù)+下中位數(shù)）的一半域庇。

具體代碼如下：

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

·輸出鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)

可以定義兩個(gè)指針听皿，第一個(gè)指針從鏈表的頭指針開始遍歷向前走k-1步宽档，第二個(gè)指針保持不動(dòng)；從第K步開始又厉，第二個(gè)指針也開始從鏈表的頭指針開始遍歷椎瘟。由于兩個(gè)指針的距離保持在k-1肺蔚，當(dāng)?shù)谝粋€(gè)指針到達(dá)鏈表的尾節(jié)點(diǎn)時(shí)候，第二個(gè)指針正好是倒數(shù)第K個(gè)節(jié)點(diǎn)璧诵。

具體實(shí)現(xiàn)如下：

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

這是主要的幾種應(yīng)用段只，之所以要寫出這幾種寫法赞枕，一方面是介紹快慢指針坪创，另一方面是提出下面的幾道在leetcode上見到的題都是用快慢指針來解決問題的姐赡。

快慢指針的習(xí)題參考

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.

我們這道題就可以借助快慢指針進(jìn)行解決：
先用快慢指針將整個(gè)鏈表一分為二，在將第二個(gè)子鏈表進(jìn)行倒序求解危喉，最后合并的到最終的結(jié)果：

/**
 * 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;
        //將第二部分鏈表反轉(zhuǎn)
        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;
        }
    }
};

第一部分就是使用的快慢指針進(jìn)行的運(yùn)算，通過移動(dòng)指針严蓖，最后fast指針指向終點(diǎn)颗胡，而slow指向中點(diǎn)，通過這個(gè)中點(diǎn)哑蔫，可以將整條鏈表分為兩部分手素，之后就可以對(duì)這兩部分進(jìn)行操作了瘩蚪。

第二部分就是對(duì)剛才分出來的鏈表的后半部分進(jìn)行逆轉(zhuǎn)操作疹瘦，比如我們?cè)仁茿->B->C的鏈表，我們要變成C->B->A邓嘹，我們可以看出來汹押，要發(fā)生逆轉(zhuǎn)的話起便，順序是發(fā)生改變的，那么意味著我們需要三個(gè)指針來進(jìn)行調(diào)整妙痹，分別是當(dāng)前節(jié)cur怯伊，以及前一個(gè)節(jié)點(diǎn)pre耿芹，和后一個(gè)節(jié)點(diǎn)nextnode，實(shí)現(xiàn)如下：

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

最后一部分就是實(shí)現(xiàn)鏈表的插入即可媚送，即按照題目中的要求將兩個(gè)鏈表一次插入即可。

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?

這道題除了讓判斷是否為回文塘偎，還對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行了限制吟秩，因此我們可以聯(lián)想到之前所說的快慢指針將整個(gè)鏈表分為兩部分涵防，之后再將后面的鏈表進(jìn)行反轉(zhuǎn)沪铭，再進(jìn)行比較即可杀怠。
具體步驟就不詳細(xì)說明了，把代碼貼出來僅供參考

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

以上就是對(duì)于快慢指針的學(xué)習(xí)