我的书签
添加书签
移除书签Reverse Linked List
Question
- leetcode: Reverse Linked List | LeetCode OJ
-
lintcode: (35) Reverse Linked List
- Reverse a linked list.
-
- Example
- For linked list 1->2->3, the reversed linked list is 3->2->1
-
- Challenge
- Reverse it in-place and in one-pass
-
- Reverse a linked list.
題解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, 翻轉相鄰兩個節點之前保存下一節點的值，分析如下圖所示：
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
6. 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
20. 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;
22. 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;
21. 22. return head;
23. }
24. }
源碼分析
題解中基本分析完畢，代碼中的prev賦值操作精煉，值得借鑒。
複雜度分析
遍歷一次鏈表，時間複雜度為 O(n), 使用了輔助變數，空間複雜度 O(1).
題解2 - 遞迴
遞迴的終止步分三種情況討論：
1. 原鏈表為空，直接返回空鏈表即可。
2. 原鏈表僅有一個元素，返回該元素。
3. 原鏈表有兩個以上元素，由於是單向鏈表，故翻轉需要自尾部向首部逆推。
由尾部向首部逆推時大致步驟為先翻轉當前節點和下一節點，然後將當前節點指向的下一節點置空(否則會出現死循環和新生成的鏈表尾節點不指向空)，如此遞迴到頭節點為止。新鏈表的頭節點在整個遞迴過程中一直沒有變化，逐層向上返回。
Python
1. """
2. Definition of ListNode
3. 4. class ListNode(object):
5. 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
29. 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;
32. 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;
21. 22. return newHead;
23. }
24. }
源碼分析
case1 和 case2 可以合在一起考慮，case3 返回的為新鏈表的頭節點，整個遞迴過程中保持不變。
複雜度分析
遞迴嵌套層數為 O(n), 時間複雜度為 O(n), 空間(不含函數堆疊空間)複雜度為 O(1).
Reference
- 全面分析再動手的習慣：鏈表的反轉問題（遞迴和非遞迴方式） - 木棉和木槿 - 博客園
- data structures - Reversing a linked list in Java, recursively - Stack Overflow
- 反轉單向鏈表的四種實現（遞迴與非遞迴，C++） | 寧心勉學，慎思篤行
- iteratively and recursively Java Solution - Leetcode Discuss
