# Linked list Bubblesort
contributed by <`Feng270`>
GitHub: [linkedlist_bubblesort](https://github.com/Feng270/linkedlist_bubblesort.git)
## 題目要求
此次補考題目第一題為給定一個 single linked list 的 node 定義如下：
```clike=c=
typedef struct __node {
int val;
struct __node *next;
} node;
```
寫出 sort 函式以不更動 val 值為限，對 linked list 做 bubblesort。
## 思路
這題乍看之下不難，但實際寫起來會發現很多的細節沒有注意到，例如一般在考慮 linked list 的時候通常不會想到會有 loop 的出現，而這裡的 loop 不單單只有環狀 linked list 更會有以下的情況產生，這時候一路到底的走訪方式會陷入無窮回圈...
[1]
有幾個問題如下：
1. 最基本的 linked list 複習
2. 克服 loop 的情況
3. 若修改 head 時 function 需要使用 pointer to pointer，以下分幾個部分來一一說明。
### Linked list loop 偵測
首先討論的是 loop 的偵測，這裡使用的是名為 `Floyd’s Cycle-Finding` 的演算法，其中概念很簡單，設兩個 pointer 名為 slow 以及 fast 兩個都從 head 開始走，slow 每次只走一步，而 fast 一次走兩步，假設有 loop 存在時 slow 終會與 fast 指到相同的節點。
以上圖為例，slow 與 fast 走訪節點如下表，得知在第 5 次迭代時會偵測到 loop 發生。
|迭代|slow|fast|
|-|-|-|
|1|1|1|
|2|2|3|
|3|3|5|
|4|4|3|
|5|5|5|
但有另一個問題出現，在 bubblesort 中會希望能夠知道整個 linked list 的長度使得程式撰寫較容易，而顯然以上的做法並沒有辦法知道什麼時候 linked list 會進入 loop，因而無法計算真正的長度，但真的是如此嗎？
今天我們假設 head 到 loop 起點的距離爲 `a`，而 loop 起點到相遇點的距離爲 `b`，相遇點回到 loop 起點的距離爲 `c`，因爲 fast 是 slow 的兩倍速度，因此 fast 走過的距離 = slow 走過距離的兩倍，slow 走的距離爲 `a + b`，fast則是 `a + b + c + b`可得以下推導：
$\quad 2slow = fast$
$\quad 2(a + b) = a + b + c +b$
$\quad a = c$
得證相遇時回到 loop 起點的距離是 head 到 loop 起點的距離，所以我們可以利用這個特性，找到 loop 起點，並分別計算 loop 內節點個數，再與 loop 外節點個數加總就是總長度了。
### Bubble Sort[2]
Bubble sort 可以簡單表示為下圖，每次迭代都會比較自己與下一個節點，以此圖來說大者會被 swap 到最後，直到所有節點被迭代過一次
### 更正 loop
Singal linked list 有個缺點是不知道上一個節點是誰，這時候我們在 swap 的時候會先將上個節點記下來，但是在 loop 的情況下（如上圖），第 2 個節點會有兩個上節點，若用一般的 swap 方法並不會記住 5 這個節點，只會記到 1 而這樣有一個問題，當節點 1 與節點 2 互相 swap 時，節點 5 的 next pointer 會被指到新的節點 1（也就是舊的節點 2），如下表示：
```
原先的 list
n1 -> n2 -> n3
| |
n5 <- n4
Swap 之後的 list
n2 -> n1 -> n3
| |
<---- n5 <- n4
```
要解決這個問題的話就必須先記住還沒 swap 前的 loop 起點，最後完成排序後再將最尾巴的 next pointer 指回正確的位置。
## 實作
有了上面的基礎，我們可以來實作 linked list 的 bubble sort，總共分成四個部分，分別是
* 產生一個 loop linked list
* 找到這個 linked list 的長度
* 進行 bubble sort
* 印出結果
以下將會一一介紹
### 產生一個 loop linked list
這裡使用了 C 的亂數產生器來產生一個 linked list，並手動指了最後節點的 next pointer 到任一其他節點
```clike=C=
// 先建立 head 節點
node *head = malloc(sizeof(node)),*now,*prev;
head->val=1;
int i;
srand(time(NULL));
// 產生額外10個節點
for (i=0;i<10;i++) {
now = malloc(sizeof(node));
now->val = rand()%100;
if (i==0) {
head->next = now;
prev = now;
}
else {
prev->next = now;
prev = now;
}
}
// Create a loop.
now->next=head->next->next->next;
```
### 找到這個 linked list 的長度
這裡可以分成兩個情況來討論，有 loop 以及沒有 loop 的情況，一開始便設有 slow 以及 fast 兩個 pointer，若一次走一步的 slow 與一次走兩步的 fast 相遇，則進入 loop 的運算，反之如果不存在 loop 那就只有 count++ 而已。
而 loop 中要怎麼計算長度呢？既然我們知道 slow 與 fast 相遇的節點一定在 loop 中，那麼只要一直走訪 next 節點，是必會回到原本 slow 與 fast 相遇的節點，也可得知 loop 內的長度了。
另外使用上述的方法，當 slow 與 fast 相遇時，讓 slow 從 head 開始，與 fast 都一次走一步，相遇的點即為 loop 的起點，計算 slow 走的長度為進入 loop 前的長度。
```clike=c=
int findlength(node *head) {
node *fast = head,*slow = head;
int count=0;
while(slow!=NULL) {
count++;
slow = slow->next;
if (fast->next!=NULL && fast->next->next!=NULL){
fast = fast->next->next;
// If loop existed.
if (slow==fast) {
node *tmp = slow;
int countloop = 1;
while (tmp->next!=slow) {
// counting nodes in loop
countloop++;
tmp = tmp->next;
}
slow = head;
count = 0;
while(slow!=fast) {
slow = slow->next;
fast = fast->next;
// counting nodes outside loop
count++;
}
count += countloop;
return count;
}
}
}
return count;
}
```
### 進行 bubble sort
有了長度之後就可以方便的進行排序了，底下有幾點要注意
* 由於會改到傳入的 head，因此必須定義成 pointer to pointer
* 首先為了防止 loop 的終點改變，必須先在排序前走訪過所有節點並記下 loop 的終點（此處為loopend）
* 中間 swap 的部分需要很清楚指標的使用，而且 head 節點需要特別處理
* 排序完之後檢查是否為 loop 是的話更正 next pointer
```clike=c=
void bubblesort(node **head,int length) {
int i,j;
node *now , *prev ,*loopend = NULL;
// 記錄最後一個節點指向的節點，若不是 NULL 即為 loop
for (i = 0,now = *head;i<length;i++,now = now->next)
loopend = now->next;
for (i = 0;i<length;i++) {
now = *head, prev = *head;
for (j = 0;j<length-1;j++) {
if (now->val > now->next->val) {
if (now == loopend)
loopend = now->next;
else if (now->next == loopend)
loopend = now;
// Swap node
node *tmp = now->next;
now->next = tmp->next;
tmp->next = now;
if (now == *head){
*head = tmp;
prev = tmp;
}
else {
prev->next = tmp;
prev = prev->next;
}
}
else {
now = now->next;
if (j!=0)
prev = prev->next;
}
}
}
// If loop existed, correct the next pointer.
if (now->next!=NULL)
now->next=loopend;
}
```
### 印出結果
用迴圈根據長度印出 linked list，此處使用長度以免陷入 loop
```clike=c=
void printresult(node *head,int length) {
node *now;
int i;
for (now=head,i=0;i<length-1;now=now->next,i++)
printf("%d,",now->val);
printf("%d\n",now->val);
}
```
## 結論
透過這次的補考，真的是在複習以前“曾經”學過的東西，可是我光不加 loop 的linked list 就寫的不太順了，不透過編譯器也沒辦法確保 code 不會出問題，透過這次的補考把該有的找回來，另外以前在寫 linked list 時也沒有想過會有 loop 的出現，還想說寫好 bubble sort 就可以交差，後期甚至花了許多時間想 loop 到底要怎麼偵測及處理。
## 參考資料
1. [Find length of loop in linked list - GeeksforGeeks](http://www.geeksforgeeks.org/find-length-of-loop-in-linked-list/)
2. [Linked List Sort - npes87184.github.io](https://npes87184.github.io/演算法/2015/09/12/linkedListSort.html)
3. [Linked List Cycle| LeetCode题解](https://siddontang.gitbooks.io/leetcode-solution/content/linked_list/linked_list_cycle.html)
Sign in with Wallet
Connect another wallet