Reverse Linked List

LeetCode

what is wrong with this code?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return nullptr;
        return rec(head);
    }
    ListNode* rec(ListNode* head) {
        if (head->next == nullptr) return head;
        ListNode* next = head->next;
        ListNode* newHead = rec(next);
        next->next = head;
        return newHead;
    }
};

---

The major problem lies here, next->next = head; this will cause a cycle in the linked list, and the function will never terminate. To fix this, we need to set head->next to nullptr after the recursive call.

    ListNode* rec(ListNode* head) {
        if (head->next == nullptr) return head;
        ListNode* next = head->next;
        ListNode* newHead = rec(next);
        next->next = head;
        head->next = nullptr;
        return newHead;
    }

in addition, it can be used in the same function, following the principle of loop invariant: 1. the return value is always the new head of the reversed linked list 2. we assume that calling func(next) will reverse order of all nodes after next, and return the new head of the reversed linked list. 3. after finishing this call, we want to make next -> head, and remove head -> next, so that the linked list is reversed correctly.

    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr) return head;
        ListNode* next = head->next;
        ListNode* newHead = reverseList(next);
        head->next = nullptr;
        next->next = head;
        return newHead;
    }

or sliding window approach:

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }