206. Reverse Linked List

Description

The problem involves reversing a singly linked list. Given the head of a singly linked list, the task is to reverse the list and return the new head.

Intuition

To reverse the linked list, we can traverse through the list while adjusting the next pointers of each node to point to its previous node. By maintaining pointers to the previous and current nodes, we can effectively reverse the direction of the list as we iterate through it.

Approach

1. Edge Case: If the list is empty (i.e., head is None), return None immediately.
2. Initialization: Start with prev as the head of the list and curr as the second node (head.next).
3. Iteration: Traverse the list using a while loop until curr becomes None. During each iteration: - Store the next node temporarily (temp). - Change the next pointer of curr to point to prev. - Move prev and curr one step forward.
4. Finalize: After the loop, set head.next to None to mark the end of the list, and return prev, which will now be the new head of the reversed list.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the linked list. Each node is visited exactly once.

Space Complexity:

O(1), as the reversal is done in-place without using any extra space except for a few pointers.

Code

C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return head;
        ListNode* prev = head;
        ListNode* curr = head->next;
        while (curr != nullptr) {
            ListNode* temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        head->next = nullptr;
        return prev;
    }
};

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        prev = head
        curr = head.next
        while curr is not None:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        head.next = None
        return prev

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode prev = head;
        ListNode curr = head.next;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        head.next = null;
        return prev;
    }
}

JavaScript

var reverseList = function(head) {
    
    if(head === null) return head;
    let prev = head;
    let curr = prev.next;
    while(curr !== null){
        let temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    head.next = null
    return prev;
};