連結串列演算法經典題
theme: channing-cyan highlight: a11y-light
由於我們在講解的過程中會設計無環單鏈表和有環單鏈表,那麼我們先建立兩個連結串列
/*連結串列*/struct ListNode { int data;
struct ListNode *next;
struct ListNode *pre;
};
無環連結串列
struct ListNode* constructList(void)
{ //頭結點定義
struct ListNode *head = NULL;
//記錄當前結點
struct ListNode *cur = NULL;
for (int i = 0; i < 8; i++) {
struct ListNode *node = malloc(sizeof(struct ListNode));
node->data = i;
//頭結點為空,新結點即為頭結點
if (head == NULL) {
head = node;
} else {//當前結點的next為新結點
cur ->next = node;
}
//設定當前結點為新結點
cur = node;
}
return head;
}
有環連結串列
``` struct ListNode constructCycleList(void) { //頭結點定義 struct ListNode head = NULL; //記錄當前尾結點 struct ListNode cur = NULL; //環結點入口 struct ListNode cycle = NULL;
for (int i = 0; i < 8; i++) {
struct ListNode *node = malloc(sizeof(struct ListNode));
node->data = i;
if (i == 3) {//第4個為環入口
cycle = node;
}
//頭結點為空,新結點即為頭結點
if (head == NULL) {
head = node;
} else {//當前結點的next為新結點
cur->next = node;
}
//設定當前結點為新結點
cur = node;
if (i == 7) {
cur->next = cycle;
}
}
return head;
} ```
1. 連結串列的倒數第K個節點
問題描述:
輸入一個連結串列,輸出該連結串列中倒數第k個結點。為了符合大多數人的習慣,本題從1開始計數,即連結串列的尾結點是倒數第1個結點。例如一個連結串列有6個結點,從頭結點開始它們的值依次是1、2、3、4、5、6。這個連結串列的倒數第3個結點是值為4的結點,需要保證時間複雜度。
演算法思路:
設定兩個指標p1,p2,從頭到尾開始出發,一個指標先出發k個節點,然後第二個指標再進行出發,當第一個指標到達連結串列的節點的時候,則第二個指標表示的位置就是連結串列的倒數第k個節點的位置。
程式碼如下:
struct ListNode* findKth(struct ListNode *head, int k)
{
struct ListNode* cur = head;
struct ListNode* now = head;
int i = 0;
while (cur!=NULL&&i++<k) {
cur = cur->next;
}
while (cur!=NULL) {
now =now->next;
cur =cur->next;
}
return now;
}
總結:當我們用一個指標遍歷連結串列不能解決問題的時候,可以嘗試用兩個指標來遍歷連結串列。可以讓其中一個指標遍歷的速度快一些(比如一次在連結串列上走兩步),或者讓它先在連結串列上走若干步。
2.從尾到頭列印連結串列(遞迴和非遞迴)
問題描述:
輸入一個單鏈錶鏈表,從尾到頭列印連結串列每個節點的值。輸入描述:輸入為連結串列的表頭;輸出描述:輸出為需要列印的“新連結串列”的表頭。
演算法思路:
首先我們想到從尾到頭打印出來,由於單鏈表的查詢只能從頭到尾,所以可以想出棧的特性,先進後出。所以非遞迴可以把連結串列的點全部放入一個棧當中,然後依次取出棧頂的位置即可。
程式碼如下:(遞迴方法)
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL || head->next == NULL) return head;
struct ListNode *nextNode = head->next;
struct ListNode *reverseNode =reverseList(nextNode);
nextNode->next = head;
head->next = NULL;
return reverseNode;
}
3.如何判斷一個連結串列有環
問題描述:
有一個單向連結串列,連結串列當中有可能出現“環”,如何用程式判斷出這個連結串列是有環連結串列? 不允許修改連結串列結構。時間複雜度O(n),空間複雜度O(1)。
演算法思路:
首先建立兩個指標1和2,同時指向這個連結串列的頭節點。然後開始一個大迴圈,在迴圈體中,讓指標1每次向下移動一個節點,讓指標2每次向下移動兩個節點,然後比較兩個指標指向的節點是否相同。如果相同,則判斷出連結串列有環,如果不同,則繼續下一次迴圈。
說明 :在迴圈的環裡面,跑的快的指標一定會反覆遇到跑的慢的指標 ,比如:在一個環形跑道上,兩個運動員在同一地點起跑,一個運動員速度快,一個運動員速度慢。當兩人跑了一段時間,速度快的運動員必然會從速度慢的運動員身後再次追上並超過,原因很簡單,因為跑道是環形的
程式碼如下:
bool isLoopList(struct ListNode* head)
{
//使用快慢指標,慢指標每次向前一步,快指標每次兩步
struct ListNode* slowPoint = head;
struct ListNode* fastPoint = head;
while (fastPoint != NULL && fastPoint->next != NULL) {
slowPoint = slowPoint->next;
fastPoint = fastPoint->next;
if (fastPoint->next != NULL) {
fastPoint = fastPoint->next;
//兩指標相遇則有環
if (slowPoint == fastPoint) {
return true;
}
}
}
return false;
}
4.連結串列中環的大小
問題描述
有一個單向連結串列,連結串列當中有可能出現“環”,那麼如何知道連結串列中環的長度呢?
演算法思路
由如何判斷一個連結串列有環可以知道,快慢指標可以找到連結串列是否有環存在,如果兩個指標第一次相遇後,第二次相遇是什麼時候呢?第二次相遇是不是可以認為快的指標比慢的指標多跑了一個環的長度。所以找到第二次相遇的時候就找到了環的大小。
程式碼如下
``` //首先找出相遇時候的環節點,然後再次到此節點則表示環大小 struct ListNode cycleNode(struct ListNode head) { //使用快慢指標,慢指標每次向前一步,快指標每次兩步 struct ListNode slowPoint = head; struct ListNode fastPoint = head; while (fastPoint != NULL && fastPoint->next != NULL) { slowPoint = slowPoint->next; fastPoint = fastPoint->next; if (fastPoint->next != NULL) { fastPoint = fastPoint->next; //兩指標相遇則有環 if (slowPoint == fastPoint) { return slowPoint; } } } return NULL; }
int getCycleLength(struct ListNode *head) {
struct ListNode *node = cycleNode(head);
//node為空則代表連結串列無環
if (node == NULL) {
return 0;
}
int length = 1;
struct ListNode* currentNode = node->next;
//再次相遇則迴圈結束
while (currentNode != node) {
length++;
currentNode = currentNode->next;
}
printf("cycle length is %d",length);
return length;
} ```
5.連結串列中環的入口結點
問題描述
給一個連結串列,若其中包含環,請找出該連結串列的環的入口結點,否則,輸出null。
演算法思路
如果連結串列存在環,那麼計算出環的長度n,然後準備兩個指標pSlow,pFast,pFast先走n步,然後pSlow和pFase一塊走,當兩者相遇時,即為環的入口處;所以解決三個問題:如何判斷一個連結串列有環;如何判斷連結串列中環的大小;連結串列中環的入口結點。實際上最後的判斷就如同連結串列的倒數第k個節點。
程式碼如下
struct ListNode* cycleListFirstNode(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* now = head;
int cycleLength = getCycleLength(head);
int i = 0;
while (cur != NULL && i++ < cycleLength) {
cur = cur->next;
}
while (cur != now) {
now = now->next;
cur = cur->next;
}
printf("cycle 入口 node value is %d",now->data);
return now;
}