Linked List - Reverse a Linked List

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

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

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

Input: head = []
Output: []

Solution 1 - Iterative approach
Solution 2 - Recursive approach

The key idea is to traverse the list and reverse the next pointer of each node to point to its previous node. We maintain three pointers: prev, curr, and next.

Initialize prev = null and curr = head.
While curr is not null, save curr.next in a temporary variable, then point curr.next to prev.
Advance prev to curr and curr to the saved next node.
After the loop, prev is the new head of the reversed list.

class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class ReverseLinkedList { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // save next curr.next = prev; // reverse pointer 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, since we visit each node once.
Space complexity: O(1) as we only use a constant number of pointers.

In the recursive approach, we recurse to the end of the list and then fix the pointers on the way back.

Base case: if head == null or head.next == null, return head (it is the new head).
Recursively reverse the rest of the list starting from head.next.
After the recursive call returns, head.next is the last node of the reversed sublist. Set head.next.next = head to make it point back to the current node.
Set head.next = null to avoid a cycle and return the new head.

public class ReverseLinkedList { public ListNode reverseListRecursive(ListNode head) { // Base case: empty list or single node if (head == null || head.next == null) { return head; } // Reverse the rest of the list ListNode newHead = reverseListRecursive(head.next); // Make head.next point back to head head.next.next = head; head.next = null; return newHead; } }

Complexity Analysis:

Time complexity: O(n) since every node is visited exactly once through the recursion.
Space complexity: O(n) due to the recursion call stack, which can go n levels deep.

Contents

Complexity Analysis:

Complexity Analysis: