Reverse Linked List

Question

  1. Reverse a linked list.
  3. Example
  4. For linked list 1->2->3, the reversed linked list is 3->2->1
  6. Challenge
  7. Reverse it in-place and in one-pass

題解1 - 非遞迴

聯想到同樣也可能需要翻轉的數組，在數組中由於可以利用下標隨機訪問，翻轉時使用下標即可完成。而在單向鏈表中，僅僅只知道頭節點，而且只能單向往前走，故需另尋出路。分析由1->2->3變為3->2->1的過程，由於是單向鏈表，故只能由1開始遍曆，1和2最開始的位置是1->2，最後變為2->1，故從這裡開始尋找突破口，探討如何交換1和2的節點。

  1. temp = head->next;
  2. head->next = prev;
  3. prev = head;
  4. head = temp;

要點在於維護兩個指針變量prev和head, 翻轉相鄰兩個節點之前保存下一節點的值，分析如下圖所示：

Reverse Linked List

  1. 保存head下一節點
  2. 將head所指向的下一節點改為prev
  3. 將prev替換為head，波浪式前進
  4. 將第一步保存的下一節點替換為head，用於下一次循環

Python

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     # @param {ListNode} head
  9.     # @return {ListNode}
  10.     def reverseList(self, head):
  11.         prev = None
  12.         curr = head
  13.         while curr is not None:
  14.             temp = curr.next
  15.             curr.next = prev
  16.             prev = curr
  17.             curr = temp
  18.         # fix head
  19.         head = prev
  21.         return head

C++

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* reverse(ListNode* head) {
  12.         ListNode *prev = NULL;
  13.         ListNode *curr = head;
  14.         while (curr != NULL) {
  15.             ListNode *temp = curr->next;
  16.             curr->next = prev;
  17.             prev = curr;
  18.             curr = temp;
  19.         }
  20.         // fix head
  21.         head = prev;
  23.         return head;
  24.     }
  25. };

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.     public ListNode reverseList(ListNode head) {
  11.         ListNode prev = null;
  12.         ListNode curr = head;
  13.         while (curr != null) {
  14.             ListNode temp = curr.next;
  15.             curr.next = prev;
  16.             prev = curr;
  17.             curr = temp;
  18.         }
  19.         // fix head
  20.         head = prev;
  22.         return head;
  23.     }
  24. }

源碼分析

題解中基本分析完畢，代碼中的prev賦值操作精煉，值得借鑒。

複雜度分析

遍歷一次鏈表，時間複雜度為 O(n), 使用了輔助變數，空間複雜度 O(1).

題解2 - 遞迴

遞迴的終止步分三種情況討論：

  1. 原鏈表為空，直接返回空鏈表即可。
  2. 原鏈表僅有一個元素，返回該元素。
  3. 原鏈表有兩個以上元素，由於是單向鏈表，故翻轉需要自尾部向首部逆推。

由尾部向首部逆推時大致步驟為先翻轉當前節點和下一節點，然後將當前節點指向的下一節點置空(否則會出現死循環和新生成的鏈表尾節點不指向空)，如此遞迴到頭節點為止。新鏈表的頭節點在整個遞迴過程中一直沒有變化，逐層向上返回。

Python

  1. """
  2. Definition of ListNode
  4. class ListNode(object):
  6.     def __init__(self, val, next=None):
  7.         self.val = val
  8.         self.next = next
  9. """
  10. class Solution:
  11.     """
  12.     @param head: The first node of the linked list.
  13.     @return: You should return the head of the reversed linked list.
  14.                   Reverse it in-place.
  15.     """
  16.     def reverse(self, head):
  17.         # case1: empty list
  18.         if head is None:
  19.             return head
  20.         # case2: only one element list
  21.         if head.next is None:
  22.             return head
  23.         # case3: reverse from the rest after head
  24.         newHead = self.reverse(head.next)
  25.         # reverse between head and head->next
  26.         head.next.next = head
  27.         # unlink list from the rest
  28.         head.next = None
  30.         return newHead

C++

  1. /**
  2.  * Definition of ListNode
  3.  *
  4.  * class ListNode {
  5.  * public:
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *
  9.  *     ListNode(int val) {
  10.  *         this->val = val;
  11.  *         this->next = NULL;
  12.  *     }
  13.  * }
  14.  */
  15. class Solution {
  16. public:
  17.     /**
  18.      * @param head: The first node of linked list.
  19.      * @return: The new head of reversed linked list.
  20.      */
  21.     ListNode *reverse(ListNode *head) {
  22.         // case1: empty list
  23.         if (head == NULL) return head;
  24.         // case2: only one element list
  25.         if (head->next == NULL) return head;
  26.         // case3: reverse from the rest after head
  27.         ListNode *newHead = reverse(head->next);
  28.         // reverse between head and head->next
  29.         head->next->next = head;
  30.         // unlink list from the rest
  31.         head->next = NULL;
  33.         return newHead;
  34.     }
  35. };

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.     public ListNode reverse(ListNode head) {
  11.         // case1: empty list
  12.         if (head == null) return head;
  13.         // case2: only one element list
  14.         if (head.next == null) return head;
  15.         // case3: reverse from the rest after head
  16.         ListNode newHead = reverse(head.next);
  17.         // reverse between head and head->next
  18.         head.next.next = head;
  19.         // unlink list from the rest
  20.         head.next = null;
  22.         return newHead;
  23.     }
  24. }

源碼分析

case1 和 case2 可以合在一起考慮，case3 返回的為新鏈表的頭節點，整個遞迴過程中保持不變。

複雜度分析

遞迴嵌套層數為 O(n), 時間複雜度為 O(n), 空間(不含函數堆疊空間)複雜度為 O(1).

Reference