資料結構與算法（一）連結清單

• 連結清單
• • 定義
  • • 作用
    • 底層結構
  • 連結清單的分類
  • • 單連結清單
    • • 結構
      • 頭結點
      • 尾結點
      • 時間複雜度
    • 循環連結清單
    • • 定義
    • 雙向連結清單
  • 算法
  • • 擷取連結清單的中位數
    • 查找單連結清單中的倒數第K個結點
    • 求環形連結清單入口點
    • 判斷兩個連結清單是否交叉
    • 連結清單反轉

連結清單

定義

作用

連結清單：通過指針将零散的記憶體塊連結起來。

底層結構

結構：

記憶體塊：為連結清單的“結點”，裡面存儲了資料

後繼指針：指向下一個結點的位址；

圖檔:

連結清單的分類

單連結清單

結構

記憶體塊(連結清單的結點)+後繼指針next(指向下一個結點)；

頭結點

連結清單中第一個結點，其記錄連結清單中的基位址；

尾結點

連結清單中的最後一個結點，其next指針指向NULL;

時間複雜度

删除和插入：都隻需要改變相鄰結點的next指針指向即可，時間複雜度為O(1)；

随機通路：不能直接通路到第K個位置，隻能通過頭結點一個一個的查找，是以時間複雜度為O(n)；

循環連結清單

定義

循環連結清單：就是單連結清單的尾結點指針指向了頭結點

雙向連結清單

直接輸入1次#，并按下space後，将生成1級标題。

輸入2次#，并按下space後，将生成2級标題。

以此類推，我們支援6級标題。有助于使用

TOC

文法後生成一個完美的目錄。

算法

擷取連結清單的中位數

char	GetMid(Node* const head)
{
	Node *fast = head, *slow = head;
	while (fast && slow) //保持移動
	{
		if (fast->pNext == NULL) //連結清單有頭結點時，
			return slow->data;
		else if(fast->pNext != NULL && fast->pNext->pNext == NULL)
			return (slow->data + slow->pNext->data) / 2;
		else
		{
			slow = slow->pNext;
			fast = fast->pNext->pNext;
		}
	}
}

           

查找單連結清單中的倒數第K個結點

Node*	RGetKthNode(Node* const head, int k)
{
	if (head == NULL)
		return NULL;

	Node *fast = head, *slow = head;
	for (int i = 0; i < k - 1; i++)
	{
		fast = fast->pNext;
		if (fast == NULL) //？應該隻是確定fast不為空，不能保證K是否超對外連結表長度
			return NULL;
	}

	while (fast->pNext != NULL) //條件不符合，代表fast到達尾結點，此時slow就指向K位置的結點
	{
		fast = fast->pNext;
		slow = slow->pNext;
	}
	return slow;
}
           

求環形連結清單入口點

參考1

參考2

題目：給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。

• 分解
• 判斷是否為環形連結清單
  • 通過快慢指針，來判斷。
  • 快慢指針都從頭結點出發，進行連結清單的周遊。快指針每次前進2個結點，慢指針每次前進1個結點。
  • 當快指針為空，或者快指針的後繼指針為空時，則說明此連結清單為單連結清單；
  • 若快指針與慢指針相遇，或者快指針的後繼指針指向慢指針時(|| slow == fast->pNext)，說明此連結清單為循環連結清單；
• 如何擷取入口
  • 環形連結清單分為入口點就是頭結點和入口點是中間結點
  • 入口點為頭結點：
    • 因為快指針速度是慢指針的2倍，當快指針走完一圈，慢指針在圈的中點；當慢指針走完一圈，快指針已經走完兩圈；此時在頭結點處相遇，相遇點就是入口點，傳回頭結點指針即可

      

  • 入口點為中間結點
    • 快慢指針相遇時，慢指針一定還沒有走完一圈。

  我們假設連結清單的起始點到環的入口點的距離為L，環的周長為R，環的入口點到快慢指針的相遇位置的距離為X（圖中紅色箭頭标注的就是快慢指針的相遇點）。

  快指針走的距離：F = L+X+nR

  慢指針走的距離：S = L+X

  因為快指針走的距離是慢指針的兩倍，是以F = 2S。

  L+X+nR = 2 * (L + X)

  L = nR - X

當n = 1時，也就是快指針走了一圈之後，在第二圈的時候遇見了慢指針，L = R - X

也就是，當連結清單指針一個指向頭結點，一個指向相遇點，二者分别循環前進一個機關，直到二者相遇即可找到入口點。

Node*	IsCircle(Node* const head)
{
	if (head == NULL)
		return NULL;

	//判斷是否環形連結清單
	Node *fast = head, *slow = head;
	while (fast != NULL && fast->pNext != NULL) //此處違反條件時可能fast為空或者fast->pNext為空，或者二者都為空
	{
		slow = slow->pNext; //慢指針每次前進一個結點
		fast = fast->pNext->pNext; //快指針每次前進兩個結點
		
		if (slow == fast) //相遇即為循環連結清單，得到相遇點
			break;
		else
			return NULL; //為單連結清單
	}

	//此時fast和slow都代表着相遇點

	//相遇點就是頭結點時，直接傳回

	if (head != slow) //入口點不是連結清單的頭結點時，找到相遇點
	{
		slow = head;
		while (slow != fast)
		{
			slow = slow->pNext;
			fast = fast->pNext; //注意是移動一個結點機關，而不是pNext的pNext
		}
	}

	return slow;
}
           

判斷兩個連結清單是否交叉

題目：判斷兩個連結清單是否相交。

分解：判斷兩個連結清單是否相交。思路：周遊兩個連結清單得到二者的長度，将指針指向長連結清單的A點，使得A點到尾點的長度與短連結清單長度一緻，

同時移動長短連結清單，若二者的指針指向同一個位置，則說明二者相交

bool isIntersection(Node* const head1, Node* const head2)
{
	if(head1 == head2 || NULL == head1 || NULL == head2)
		return false;
	
	Node* pTmp1 = head1, *pTmp2 = head2;
	int length1 = 0, length2 = 0;
	
	while(pTmp1++) length1++;
	while(pTmp2++) length2++;
	
	int step = length1 - length2;
	step = abs(step);
		
	pTmp1 = head1, pTmp2 = head2,length1 = 0;	
	while( (length1++) <step) pTmp1++;
	
	while((pTmp1++) != (pTmp2++))
	{
		if(pTmp1==NULLL || pTmp2 == NULL)
			return false;
	}
	
	return true;	
}
           

連結清單反轉

分解：使用三個指針，一個指針指向反轉後的連結清單，另外兩個指針用于移動和取連結清單的結點。

Node* reverseNode(Node* pHead)
{
	if(!pHead) return NULL;
	
	Node* pNew = NULL, *pCurrent = pHead, *pNext = NULLt;
	
	while(pCurrent)
	{
		pNext = pCurrent->next; //記錄待移動的結點
		pCurrent->next = pNew; //将連結清單的原順序斷掉，逆指向
		pNew = pCurrent; //将指針指向新連結清單的頭結點，以便後期插入新的
		pCurrent = pNext; //在原連結清單中移位取新的結點來進行下一次操作
	}
	return pNew;
}