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