18. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input: head = [1,2]
Output: [2,1]

Input: head = []
Output: []

Problem Breakdown:

1. We use three pointers: prev (initially null), curr (starts at head), and next (temporary). We iterate through the list, reversing each pointer.

• prev = None
  curr = head

2. While curr is not null, save the next node, reverse the current node's pointer to point to prev, then advance both prev and curr.

• while curr:
      next_node = curr.next
      curr.next = prev
      prev = curr
      curr = next_node

3. After the loop, prev points to the new head of the reversed list (the last node of the original list). curr is null.

• return prev

Summary:

Iterate through the list with three pointers. For each node, save the next reference, reverse the current node's pointer to the previous node, then advance. After traversal, prev is the new head.

Time and Space Complexity:

Time Complexity: O(n) - we visit each node exactly once.

Space Complexity: O(1) - only three pointer variables used.

Python Solution:

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

JavaScript Solution:

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

Java Solution:

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