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

題目：輸入一個單向連結清單，輸出該連結清單中倒數第k個結點。連結清單的倒數第0個結點為連結清單的尾指針。連結清單結點定義如下：

分析：為了得到倒數第k個結點，很自然的想法是先走到連結清單的尾端，再從尾端回溯k步。可是輸入的是單向連結清單，隻有從前往後的指針而沒有從後往前的指針。是以我們需要打開我們的思路。

 既然不能從尾結點開始周遊這個連結清單，我們還是把思路回到頭結點上來。假設整個連結清單有n個結點，那麼倒數第k個結點是從頭結點開始的第n-k-1個結點（從0開始計數）。如果我們能夠得到連結清單中結點的個數n，那我們隻要從頭結點開始往後走n-k-1步就可以了。如何得到結點數n？這個不難，隻需要從頭開始周遊連結清單，每經過一個結點，計數器加一就行了。

 這種思路的時間複雜度是O(n)，但需要周遊連結清單兩次。第一次得到連結清單中結點個數n，第二次得到從頭結點開始的第n­-k-1個結點即倒數第k個結點。

 如果連結清單的結點數不多，這是一種很好的方法。但如果輸入的連結清單的結點個數很多，有可能不能一次性把整個連結清單都從硬碟讀入實體記憶體，那麼周遊兩遍意味着一個結點需要兩次從硬碟讀入到實體記憶體。我們知道把資料從硬碟讀入到記憶體是非常耗時間的操作。我們能不能把連結清單周遊的次數減少到1？如果可以，将能有效地提高代碼執行的時間效率。

 如果我們在周遊時維持兩個指針，第一個指針從連結清單的頭指針開始周遊，在第k-1步之前，第二個指針保持不動；在第k-1步開始，第二個指針也開始從連結清單的頭指針開始周遊。由于兩個指針的距離保持在k-1，當第一個（走在前面的）指針到達連結清單的尾結點時，第二個指針（走在後面的）指針正好是倒數第k個結點。

 這種思路隻需要周遊連結清單一次。對于很長的連結清單，隻需要把每個結點從硬碟導入到記憶體一次。是以這一方法的時間效率前面的方法要高。

 思路一的參考代碼：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

<code>///////////////////////////////////////////////////////////////////////</code>

<code>// Find the kth node from the tail of a list</code>

<code>// Input: pListHead - the head of list</code>

<code>//        k         - the distance to the tail</code>

<code>// Output: the kth node from the tail of a list</code>

<code>ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned </code><code>int</code> <code>k)</code>

<code>{</code>

<code>      </code><code>if</code><code>(pListHead == NULL)</code>

<code>            </code><code>return</code> <code>NULL;</code>

<code>      </code><code>// count the nodes number in the list</code>

<code>      </code><code>ListNode *pCur = pListHead;</code>

<code>      </code><code>unsigned </code><code>int</code> <code>nNum = 0;</code>

<code>      </code><code>while</code><code>(pCur-&gt;m_pNext != NULL)</code>

<code>      </code><code>{</code>

<code>            </code><code>pCur = pCur-&gt;m_pNext;</code>

<code>            </code><code>nNum ++;</code>

<code>      </code><code>}</code>

<code>      </code><code>// if the number of nodes in the list is less than k</code>

<code>      </code><code>// do nothing</code>

<code>      </code><code>if</code><code>(nNum &lt; k)</code>

<code>      </code><code>// the kth node from the tail of a list</code>

<code>      </code><code>// is the (n - k)th node from the head</code>

<code>      </code><code>pCur = pListHead;</code>

<code>      </code><code>for</code><code>(unsigned </code><code>int</code> <code>i = 0; i &lt; nNum - k; ++ i)</code>

<code>       </code><code>return</code> <code>pCur;</code>

<code>}</code>

思路二的參考代碼：

34

35

36

37

38

39

<code>ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned </code><code>int</code> <code>k)</code>

<code>      </code><code>ListNode *pAhead = pListHead;</code>

<code>      </code><code>ListNode *pBehind = NULL;</code>

<code>      </code><code>for</code><code>(unsigned </code><code>int</code> <code>i = 0; i &lt; k; ++ i)</code>

<code>            </code><code>if</code><code>(pAhead-&gt;m_pNext != NULL)</code>

<code>                  </code><code>pAhead = pAhead-&gt;m_pNext;</code>

<code>            </code><code>else</code>

<code>            </code><code>{</code>

<code>                  </code><code>// if the number of nodes in the list is less than k,</code>

<code>                  </code><code>// do nothing</code>

<code>                  </code><code>return</code> <code>NULL;</code>

<code>            </code><code>}</code>

<code>      </code><code>pBehind = pListHead;</code>

<code>      </code><code>// the distance between pAhead and pBehind is k</code>

<code>      </code><code>// when pAhead arrives at the tail, p</code>

<code>      </code><code>// Behind is at the kth node from the tail</code>

<code>      </code><code>while</code><code>(pAhead-&gt;m_pNext != NULL)</code>

<code>            </code><code>pAhead = pAhead-&gt;m_pNext;</code>

<code>            </code><code>pBehind = pBehind-&gt;m_pNext;</code>

<code>      </code><code>return</code> <code>pBehind;</code>

讨論：這道題的代碼有大量的指針操作。在軟體開發中，錯誤的指針操作是大部分問題的根源。是以每個公司都希望程式員在操作指針時有良好的習慣，比如使用指針之前判斷是不是空指針。這些都是程式設計的細節，但如果這些細節把握得不好，很有可能就會和心儀的公司失之交臂。

另外，這兩種思路對應的代碼都含有循環。含有循環的代碼經常出的問題是在循環結束條件的判斷。是該用小于還是小于等于？是該用k還是該用k-1？由于題目要求的是從0開始計數，而我們的習慣思維是從1開始計數，是以首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之後再用邊界值、邊界值減1、邊界值加1都運作一次（在紙上寫代碼就隻能在心裡運作了）。

擴充：

1.輸入一個單向連結清單。如果該連結清單的結點數為奇數，輸出中間的結點；如果連結清單結點數為偶數，輸出中間兩個結點前面的一個。

為了解決這個問題，我們也可以定義兩個指針，同時從連結清單的頭結點出發，一個指針一次走一步，另一個指針一次走兩步。當走得快的指針走到連結清單的末尾時，走的慢的指針正好在連結清單的中間。

2.判斷一個單向連結清單是否形成了環形結構。

和之前的題目一樣，定義兩個指針，同時從連結清單的頭結點出發，一個指針一次走一步，另一個指針一次走兩步。如果走得快的指針追上了走得慢的指針，那麼連結清單就是環形連結清單；如果走得快的指針走到了連結清單的末尾都沒有追上第一個指針，那麼連結清單就不是環形連結清單。

碰到類似問題，當我們用一個指針周遊連結清單不能解決問題的時候，可以嘗試用兩個指針來周遊連結清單。可以讓其中一個指針周遊的速度快一些（比如一次在連結清單上走兩步），或者讓那個它先在連結清單上走若幹步。

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3402858.html，如需轉載請自行聯系原作者