演算法入門題：如何反轉一個單向鏈表？

2020 年 12 月 23 日
筆記
JAVA, Ruby

最近在 LeetCode 上面玩 鏈表 類型的題目，所以打算寫一篇文章，分享一下在做鏈表類型題目的心得。

眾所周知，玩鏈表就是玩指針，今天跟大家講解一個鏈表的入門題目，如何反轉一個單向鏈表 也是 LeetCode #206 是很熱門的一道編程題 LC#206 Reverse Linked List ，如圖：

解題理論：

想要反轉一個單向鏈表，除了當前的 head 指針外，我們還另外需要兩個輔助指針：

preNode 用於保存上一個引用的指針
nextNode 用於保存下一個引用的指針

不管你使用什麼程式語言，反轉鏈表的公式都是一樣的，主要分為以下四步：

將當前 head 引用的 next 引用傳遞給 nextNode
將當前 preNode 引用賦值給 head.next 實現反轉（重要）
移動 preNode 指針，準備進行下一次反轉
移動 head 指針，準備進行下一次反轉

使用 Java 語言表示的程式碼如下：

    public static ListNode reverseList(ListNode head) {
        ListNode next, pre = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

因為動態語言允許交叉賦值，所以使用動態語言反轉鏈表就更加的簡單，程式碼如下：

  def reverse_list(head)
      while(head != nil) 
          cur_next, head.next, pre = head.next, pre, head
          head = cur_next
      end
      pre
  end

圖解數據結構

上面程式碼和文字描述看上去可能不太直觀，我們下面通過圖文的形式展示一個單向鏈表是如何被反轉的

單向鏈表的初始狀態：

然後我們第一步，開始初始化指針，

ListNode next, pre = null

然後，執行第一步切換指引的程式碼：

next = head.next;

這時候鏈表和指針的位置改變如下圖：

當執行第二步程式碼：

head.next = pre;

這時候鏈表內的指針發生了如下的變化：

這裡可以看到 head 引用的 next 指向已經發生的反轉變化 ，這一步也是反轉鏈表最重要的一步

後面第三步，第四步就是移動 preNode，head 指針，準備為下一次元素反轉做準備了

第三步程式碼：

pre = head;

如圖：

這時候 preNode 已經跟 head 頭指針指向同一個節點，準備為下一次反轉做準備

第四步程式碼：

head = next;

看到這裡大家發現 nextNode 指針其實作用不大，就是幫助 head 同學臨時佔一個位置的，反轉指針主要依靠 preNode 和 head，反轉完成後如何：

執行到這裡，元素 1 已經被反轉過來的，只需要將以上四步執行 N 次，就可以將一個長度為 N 的鏈表全部反轉，所以這套解法的時間複雜度就是 O（n），最後只要提交程式碼，你就能打敗全國 90%的對手，不信的話可以打開 LeetCode 提交一下程式碼 (●—●)

總結

這道題非常簡單，如果你是老手的話就當幫你回顧一下反轉鏈表的解題思路，如果你是新手的話說不定能幫忙打開演算法世界的大門，覺得文章不錯的話，可以分享給朋友，最後再留一個問題，可以思考一下：

為什麼最終返回的指針是 preNode，而不是 head ？

Tags: JAVA Ruby