Reverse Linked List

    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，用于下一次循环

    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.         while (curr != NULL) {
    14.             ListNode *temp = curr->next;
    15.             curr->next = prev;
    16.             prev = curr;
    17.             curr = temp;
    18.         }
    20.         head = prev;
    22.         return head;
    23.     }
    24. };

    Java

    复杂度分析

    遍历一次链表，时间复杂度为 O(n), 使用了辅助变量，空间复杂度 O(1).

    递归的终止步分三种情况讨论：

    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.         # case3: reverse from the rest after head
    24.         # reverse between head and head->next
    25.         head.next.next = head
    26.         # unlink list from the rest
    27.         head.next = None
    29.         return newHead

    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;
    24. }

    源码分析

    case1 和 case2 可以合在一起考虑，case3 返回的为新链表的头节点，整个递归过程中保持不变。

    递归嵌套层数为 O(n), 时间复杂度为 O(n), 空间(不含栈空间)复杂度为 O(1).