PPractick

The problem

A messaging app stores a chat's messages as a singly linked list from oldest to newest, and the "newest first" view needs the list reversed in place, without allocating a second list. In a singly linked list each node only knows its successor, so reversing means redirecting every next pointer to point backwards. Doing that without losing the rest of the list takes three pointers: the part already reversed (prev), the node being processed (cur), and the part still to process (next). It's probably the most-asked linked-list question of all.

Example: 1 -> 2 -> 3 -> 4 -> 5 → 5 -> 4 -> 3 -> 2 -> 1.

Function signature

Node* reverseList(Node* head);  // returns the new head

Test cases

Input list	Output list	Explanation
1 -> 2 -> 3 -> 4 -> 5	5 -> 4 -> 3 -> 2 -> 1
1 -> 2	2 -> 1
7	7
(empty)	(empty)

(Confirm: reverse the links in place (O(1) extra space); return the new head.)

How interviewers phrase it

• "Reverse a singly linked list" (LeetCode 206), iteratively and then recursively (S.No 160).
• Variants: reverse between positions m and n (LeetCode 92), reverse in groups of k (LeetCode 25).

Clarifying questions to ask

1. In place, or may I build a new list?
2. Iterative or recursive?
3. Should the function return the new head?

Follow-ups to expect

1. "Why do you need three pointers?"
2. "What does each iteration do?"
3. "What's the new head?"
4. "How would you reverse only part of the list?"
5. "Complexity?"

Related questions

• Search in Linked List Medium
• Reverse a Doubly Linked List Medium
• Reverse a LL Medium
• Detect a loop in LL Medium
• Find the starting point in LL Medium
• Length of loop in LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in