https://leetcode.com/problems/reverse-linked-list/

Solution

Let prev and cur be 2 continuous items of the list:

prev -> cur

We cannot just assign cur->next = prev, because we will lose the information of the next node of cur. So we need to store this information to a node before do the reverse:

  • next = cur->next
  • cur->next = prev
  • prev = cur
  • cur = next

This problem has many edge cases:

  • the list is empty (i.e head == NULL)
  • the list has only one node (i.e. head->next == NULL)
  • when to stop reversing loop? => when cur == NULL.
    ListNode* reverseList(ListNode* head) {
        if (!head) return NULL;
        if (!head->next) return head;
        ListNode* cur = head->next;
        ListNode* prev = head;
        head->next = NULL;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

Runtime: O(n).

  • Recursion solution
    ListNode* reverseList(ListNode* head) {
            if (!head) return head;
            if (!head->next) return head;
            ListNode* last = reverseList(head->next);
            head->next->next = head;
            head->next = NULL;
            return last;
    }

Again we see the power of recursion. Using this technique, we can expand to

  • reverse n first item of the list:
    ListNode* successor;
    ListNode* reverseN(ListNode* head, int n) {
        if (n == 1) {
            successor = head->next;
            return head;
        }
        ListNode* last = reverseN(head->next, n-1);
        head->next->next = head;
        head->next = successor;
        return last;
    }
  • reverse item from n to m of the list (LC 92)
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m <= 1) return reverseN(head, n-m+1);
        head->next = reverseBetween(head->next, m-1, n-1);
        return head;
    }