Reverse Linked List easy

Problem Statement

Reverse a singly linked list.

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

Steps to Solve

The core idea is to iteratively reverse the links between nodes. We'll maintain three pointers:

1. prev: The previous node (initially null).
2. curr: The current node (initially head).
3. next: The next node after the current node.

In each iteration, we:

1. Store the next node.
2. Reverse the link of the curr node to point to prev.
3. Move prev and curr one step forward.

We continue this until curr becomes null, indicating we've reached the end of the list.

Explanation

Let's trace Example 1: [1,2,3,4,5]

| Iteration | prev | curr | next | List State | |-----------|-------|-------|-------|------------------------------------------| | 1 | null | 1 | 2 | null <- 1 -> 2 -> 3 -> 4 -> 5 | | 2 | 1 | 2 | 3 | null <- 1 <- 2 -> 3 -> 4 -> 5 | | 3 | 2 | 3 | 4 | null <- 1 <- 2 <- 3 -> 4 -> 5 | | 4 | 3 | 4 | 5 | null <- 1 <- 2 <- 3 <- 4 -> 5 | | 5 | 4 | 5 | null | null <- 1 <- 2 <- 3 <- 4 <- 5 |

After the loop, prev will point to the new head (5).

Code (C#)

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;

        while (curr != null) {
            next = curr.next; // Store the next node
            curr.next = prev; // Reverse the link
            prev = curr;      // Move prev forward
            curr = next;      // Move curr forward
        }

        return prev; // prev is now the new head
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use a constant amount of extra space for the pointers (prev, curr, next).