【C++】演算法集錦（6）：快慢指標

雙指標解法

這是我很喜歡的一個解法，從我第一眼看到它就很喜歡了，

什么時候會用到雙指標呢？但凡可以出現兩潭訓者更多序列的時候，就可以用這種方法了，
注意，我說的是：可以出現，有條件要上，沒有條件創造條件也要上，

直接上例子吧，這演算法太常見了，

快排

雙邊遍歷

首先啊，確定基準為4，左指標指向第一個元素，右指標指向尾巴，

右指標開始，向前遍歷，找到第一個大于基準的元素就停下，輪到左指標，同理，

當兩個指標都停下之后，將兩個指標所指向的值互換位置，

重復上述步驟直到左右指標重合，

重合之后，將基準元素與左右指標當前位置元素進行互換，

一次回圈之后，重復上述動作，對劃分出的部分再次回圈，直到每個部分都只有一個元素為止，

#include<iostream>
#include<vector>

using namespace std;

void doubleSideSort(vector<int> &vec1,int left,int right)	//序列與左右指標傳入
{
	//結束語
	if (right == left)
		return;

	//基準確定
	int flag = vec1[left];

	int keep_right = right;
	int keep_left = left;
	int change_temp;

	//當左右指標還沒重合
	while (left<right)
	{
		//左指標先走
		while (left<right && vec1[left]<=flag)
		{
			left++;
		}//當遇到比基準大的數，停下來

		//輪到右指標走
		while (left < right && vec1[right] >= flag)	//可以都等，反正最后都會歸并
		{
			right--;
		}//當遇到比基準小的數，停下來

		if (left < right)
		{
			change_temp = vec1[left];
			vec1[left] = vec1[right];
			vec1[right] = change_temp;
		}

		//然后繼續回圈
	}

	//left--;

	//接著將基準放進去，此時必定是左右相合，則左值若大于左值左邊一位，和左值左邊一位換，若小，則和左值換
	if (vec1[left] > vec1[left - 1])
	{
		vec1[keep_left] = vec1[left-1];
		vec1[left-1] = flag;
	}
	else
	{
		vec1[keep_left] = vec1[left];
		vec1[left] = flag;
	}

	doubleSideSort(vec1,0,left-1);
	doubleSideSort(vec1, right, keep_right);
}

int main()
{
	vector<int> vec1 = { 4,6,8,7,9,3,1};	//測驗用2個數測驗最直觀，因為最后都要通過這一步才能正常
	int left = 0;
	int right = vec1.size() - 1;

	doubleSideSort(vec1, left, right);

	for (; left <= right; left++)
		cout << vec1[left] << " ";
	cout << endl;

	return 0;
	
}

鏈表成環

判斷鏈表是否有環

就像那電影里的情節，男主女主在小樹林里迷路了，到處都是樹，他們兜兜轉轉，又回到了原點，
鏈表一旦成環，沒有外力的介入是繞不出來的，

我舉個栗子：

//ListNode* reverseList(ListNode* head)
//{
//    ListNode* node_temp;
//    ListNode* new_head;
//
//    node_temp = head;
//    //遍歷一個節點，就把它拿下來放到頭去
//    while (head->next != NULL)
//    {
//        //先考慮只又兩個節點的情況 
//        head = head->next;
//        new_head = head;
//        new_head->next = node_temp;
//        node_temp = new_head;
//    }
//    return new_head;
//}

我也不知道當時是哪兒來的靈感，寫出了這么個玩意兒，后來怎么著了？后來卡死了唄，就擱那兒繞圈，繞不出來了，

那要這么去判斷一個鏈表是否有環呢？
其實說簡單也簡單，快慢指標就解決了，快指標兩步走，慢指標一步走，只要兩個指標重合了，那就說明有環，因為快指標繞回來了，
時間復雜度為線性，空間復雜度為常數，
說不簡單也不簡單，因為你去判斷一個鏈表是否有環，那頂多是在測驗環節，放在發布環節未免顯得太刻意，連代碼是否安全都不能保證，

而且，有環的話一般是運行不過的，不用測，運行超時妥妥要考慮一下環的情況，一除錯就知道了，

尋找鏈表入環點

這個就比較需要腦子了，前邊那個有手就行的，

我這個人，懶了點，來張現成的圖吧，

看啊，在相遇之前呢，慢指標走的距離很好求的：L1 = D+S1;
快指標走的距離：設它在相遇前繞了n圈（n>1），那么：L2 = D+S1+n(S1+S2);

不過，還有一個等量關系，不要忽略掉，快指標的速度是慢指標的兩倍，所以：L2 = 2L1;
那么就是：n(S1+S2)-S1 = D;
再轉換一下就是：(n-1)(S1+S2)+S2 = D;

那也就是說，在相遇時候，把一個慢指標放在鏈表頭，開始遍歷，把一個慢指標放在相遇點開始轉圈，當它倆相遇的時候，就是入環點了，

其實吧，用腦子想一開始很難想出來，用手想就快多了，

環的大小就不用我多說了吧，相遇之后，定住快指標，慢指標再繞一圈，再相遇的時候就是一圈了，

合并K個有序鏈表（困難）

合并 k 個排序鏈表，回傳合并后的排序鏈表，請分析和描述演算法的復雜度，

示例:

輸入:

[
  1->4->5,
  1->3->4,
  2->6
]
輸出: 1->1->2->3->4->4->5->6

思路：

將 k 個鏈表配對并將同一對中的鏈表合并；
第一輪合并以后， k 個鏈表被合并成了 k\2個鏈表，平均長度為 2n\k，然后是 k\4個鏈表， k\8 個鏈表等等；
重復這一程序，直到我們得到了最終的有序鏈表，

代碼實作：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

尋找鏈表中的倒數第K個元素

思路也挺直接的，先讓一個指標走K步，然后從頭再放一個指標，兩個指標同時走，當前面的指標走到頭的時候，后面那個指標所在的位置就是倒數第K個元素了，

代碼我就不寫了吧，

只要序列有序，我們就應該想到快慢指標，
快慢指標有一個高級進化：滑動視窗，看看要不明天給安排上吧，