你真的懂單連結清單嗎

出處：http://februus.iteye.com/blog/1488568

首先，上一道開胃菜：怎麼判斷兩個單連結清單是否相交？ 

      我們假設兩個單連結清單分别是A（有m個結點）和B（有n個結點），當然，最容易想到的肯定是兩層循環，周遊A中的元素，然後分别與B中的元素進行比較，但是這樣做的時間複雜度達到了O(m*n)，那麼有沒有更簡單的辦法呢？肯定有！ 

      我們來看看單連結清單的性質：每個結點隻通過一個指針指向後繼結點。那麼是不是意味着兩個單連結清單如若相交，它們就隻能是Y形相交，而不可能是X形相交，亦即從第一個相同的結點開始，後面的結點全部一樣。如果能想到這個，後面的就簡單明了了：隻要A連結清單和B連結清單的最後一個結點值相等，則證明A連結清單和B連結清單相交。該算法的時間複雜度也下降到O(m+n)。 

      我們進一步來思考：怎麼找到第一個相交的元素呢？ 

      這裡就當然不能像剛才那樣，但是出發點還是一樣，我們同樣可以保證隻要兩次周遊。我們假設m > n，那麼如果我們将兩個連結清單的末尾對齊，是不是從最後一個往前看（當然單連結清單不能往前周遊，我們先這樣看）的時候，A連結清單會比B連結清單多m-n個元素，而A連結清單中的前m-n個元素可以忽略，直接從第m-n個元素開始和B連結清單一起向前周遊，比較A連結清單上第m-n+i個元素和B連結清單第i個元素（i<n）即可。第一個相同的元素即為所求。參看下圖可以幫助了解： 

      實作代碼如下： 

Java代碼   

1.     public static int findSame(FLinkedList A, FLinkedList B){  
2.         int m = A.length();  
3.         int n = B.length();  
4.         FLinkedNode aHead = A.getElem(0);  
5.         FLinkedNode bHead = B.getElem(0);  
6.         if(m >= n){  
7.             int s = m - n;  
8.             for(int i = 0; i < s; i ++){  
9.                 aHead = aHead.getNext();  
10.             } // end for  
11.             while(aHead.getNext() != null){  
12.                 if(aHead.getValue() == bHead.getValue()){  
13.                     return aHead.getValue();  
14.                 }else{  
15.                     aHead = aHead.getNext();  
16.                     bHead = bHead.getNext();  
17.                 } // end if-else  
18.             } // end while  
19.         }else{  
20.             int s = n - m;  
21.             for(int i = 0; i < s; i ++){  
22.                 bHead = bHead.getNext();  
23.             } // end for  
24.             while(aHead.getNext() != null){  
25.                 if(aHead.getValue() == bHead.getValue()){  
26.                     return bHead.getValue();  
27.                 }else{  
28.                     aHead = aHead.getNext();  
29.                     bHead = bHead.getNext();  
30.                 } // end if-else  
31.             } // end while  
32.         } // end if-else  
33.         System.out.println("沒有找到相同的元素！！");  
34.         return -1;  
35.     } // end findSame  

（代碼中的FlinkedList是本人自己實作的單連結清單，功能和系統的LinkedList差不多，方法的功能大家看名字就基本知道了，隻是它是更純粹的單連結清單而已） 

      下面來看看其它的幾個單連結清單相關的典型問題（貼代碼太占空間，這裡就隻談談思路，大家可以動手試試）： 

      單連結清單的反轉 

      如題，怎麼實作一個單連結清單A（有m個元素）的反轉呢？ 

      方案一：如果不能破壞原單連結清單，我們需要重新建立一個連結清單C，然後周遊原來的A連結清單，對C連結清單實行頭插法建表（頭插法即将新加入的結點作為連結清單的頭結點，對應的還有尾插法，即直接在連結清單末尾添加元素）； 

      方案二：如果可以破壞原單連結清單呢？暴力一點的辦法是不斷地交換相鄰的兩個元素，即首先将第一個元素通過m-1次交換使其變成連結清單的最後一個元素，然後又是同樣的方法将現任的第一個元素通過m-2次交換使其成為連結清單的倒數第二個元素，以此類推。 

      單連結清單的排序 

      就排序原理而言，個人覺得其實不用過多考慮存儲結構的問題，即不管是順序存儲還是鍊式存儲，都不影響排序的基本原理，隻是不同的存儲結構會影響不同排序方法的效率而已。因為我們完全可以誇張地将順序存儲也想象為不連續的存儲隻是它們相鄰兩者的間隙極端的小。即我們将貨物分别存在美國和中國的倉庫裡和都存放在一個倉庫裡是一樣的，隻是運費問題而已。 

      明白了這一點，那麼單連結清單的排序就和普通的數組排序沒有什麼太大的差別。我們現在要做的事就是針對性地選擇一個時間性能相對較好的排序算法。 

      我們知道的排序方法有很多：插入排序、冒泡排序、快速排序、歸并排序、堆排序以及基數排序等等，那麼這其中哪些對順序結構和鍊式結構不那麼感冒呢？熟悉這些排序的童鞋肯定知道，是插入排序和冒泡排序。其他的幾種常見排序方法就比較偏袒順序存儲結構了。是以，如果要對連結清單進行排序，我會選擇插入排序或者冒泡排序。（不太清楚這些基本排序原理的click here：http://wlh0706-163-com.iteye.com/blog/1465570） 

      删除單連結清單中的最小元素 

      我能想到的辦法就是周遊兩次：第一次找到單連結清單中最小的元素，第二次周遊删除該元素。第一次周遊的時候需要借助兩個變量，一個儲存目前的最小元素的值，另一個儲存目前最小值的位序。第二次周遊的時候當然就是删除第一次周遊得到的最小元素的位序上的元素了。 

      删除所有重複結點 

      這個一般得借助其他的資料結構了。基本思路應該是：周遊連結清單，用一個資料結構儲存目前已經周遊的元素，若下一個通路的連結清單裡的元素已經存在于已經通路的元素集合中，則删除單連結清單中的該元素，否則繼續，直至到達連結清單的末尾。儲存已經通路過的元素可以用數組，也可以用其他的。 

      判斷一個連結清單是否包含另一個連結清單 

      這個問題其實和開篇的問題一樣，隻是換了一種說法而已。是以隻要找到第一個相同的元素就可以了。 

      找出單連結清單中的倒數第K個元素 

      我們首先要確定的就是單連結清單的元素個數大于K。 

      這裡的實作思路也很巧妙：我們定義兩個指針a和b，全部指向連結清單的頭結點，然後a指針開始向後周遊，但a周遊到第K個元素的時候，b指針也開始從頭開始周遊，接下來的事你應該知道了，當a指針到達連結清單的末尾時，b指針恰好指着連結清單的倒數第K個元素。這樣的時間複雜度是O(n)。 

      推廣一下：怎麼找單連結清單中間的那個元素呢？Ok, u let me know!