Reverse Linked List Solution for Capgemini

Company: Capgemini · Difficulty: Easy · Topics: Linked List, Recursion

Problem Statement

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

The linked list is defined as:

• Each node contains a value and a reference to the next node
• The head is the first node of the linked list

Examples

Example 1:

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

Output: [5,4,3,2,1]

Explanation: The list is reversed completely.

Example 2:

Input: head = [1,2]

Output: [2,1]

Explanation: The list is reversed.

Example 3:

Input: head = []

Output: []

Explanation: Empty list remains empty.

Intuition

We can reverse the linked list by changing the direction of all the next pointers. We need to keep track of the previous, current, and next nodes during the reversal process.

Approach

Approach 1: Iterative (Optimal)

1. Initialize prev = NULL, curr = head

2. While curr is not NULL:

• Store next node: next = curr->next
• Reverse link: curr->next = prev
• Move pointers: prev = curr, curr = next

3. Return prev as new head

Approach 2: Recursive

1. Base case: if head is NULL or head->next is NULL, return head

2. Recursive call: newHead = reverseList(head->next)

3. Reverse link: head->next->next = head

4. Set head->next = NULL

5. Return newHead

Approach 3: Stack

1. Push all nodes onto a stack

2. Pop nodes to create reversed list

3. Update pointers accordingly

Dry Run

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

Iterative Approach:

• prev = NULL, curr = 1
• next = 2, curr->next = NULL, prev = 1, curr = 2
• next = 3, curr->next = 1, prev = 2, curr = 3
• next = 4, curr->next = 2, prev = 3, curr = 4
• next = 5, curr->next = 3, prev = 4, curr = 5
• next = NULL, curr->next = 4, prev = 5, curr = NULL
• Return prev = 5 → [5,4,3,2,1]

Key Insights

1. Three Pointers: Need prev, curr, and next for reversal

2. Link Reversal: curr->next = prev changes direction

3. Pointer Movement: Move prev and curr forward

4. New Head: prev becomes the new head

Edge Cases

1. Empty list: Return NULL

2. Single node: Return the same node

3. Two nodes: Simple reversal

4. Long list: Handle multiple reversals

Time and Space Complexity

• Time Complexity: O(n) - Single pass through list
• Space Complexity: O(1) - Only constant extra space used

More Capgemini coding questions