Three references, four lines, one loop. Every list-surgery question in an interview is this loop plus some bookkeeping.
Reversing a linked list is the most common warm-up question. The harder versions reverse a sublist, reverse in groups of k, rotate, or reorder. They are the same four lines with careful stitching at the ends. Learn the loop until you can write it without thinking. Then spend your attention on the joins.
List<int> and writing them back would be trivial. That is why the space limit is the real question.LinkedList<T>, a doubly linked list. It is not what these questions mean. Interviewers hand you a custom ListNode class, so you rewire Next fields by hand.prev heads the part already reversed. current is the node being flipped. next is a saved copy of the rest. Each pass does one thing: it points current.Next back at prev. Then all three move forward one place. You save next only because the flip destroys the forward link you still need.current is null.Reading the figure. Green nodes are already reversed, and prev heads them. Blue is current. Grey nodes are not touched yet. Save next first. Then one green arrow flips to point left.
current are reversed, and prev is their head. The nodes from current on are still in the original order. When current becomes null, the reversed part is the whole list. So prev is the new head. That is why the method returns prev, not head. People fumble this detail.In partial reversals, the head moves in some cases and stays in others. That branch makes the code messy. A dummy node in front of the real head removes the special case.
// 0: a filler value. Nobody reads the dummy as data, so any int works.
var dummy = new ListNode(0, head); // a node that is not part of the data
// ... do all the surgery, treating dummy as an ordinary predecessor ...
return dummy.Next; // whatever ended up first is the real head
/// <summary>A singly linked list node.</summary>
/// <param name="val">The payload. 0 by default.</param>
/// <param name="next">The following node, or null at the end.</param>
/// <example>new ListNode(1, new ListNode(2)) is the list 1 -> 2.</example>
public sealed class ListNode(int val = 0, ListNode? next = null)
{
public int Val = val; // 0 default: the payload when none is given
public ListNode? Next = next; // null marks the end of the list
}
Use a class, not a struct. A struct is copied on every assignment, so relinking would edit a copy. Avoid a record too. Its generated ToString and Equals walk Next, which is slow on long lists and overflows the stack on a cycle.
public static class TemplateA
{
/// <summary>Reverse a whole list in place.</summary>
/// <param name="head">First node, or null for an empty list.</param>
/// <returns>The head of the reversed list.</returns>
/// <example>Reverse(1 -> 2 -> 3) returns 3 -> 2 -> 1.</example>
public static ListNode? Reverse(ListNode? head)
{
ListNode? prev = null; // null: the old head will point here, ending the list
var current = head; // the next node to flip
// Invariant: nodes before current are reversed, and prev heads them.
while (current is not null)
{
var next = current.Next; // 1. save the rest before destroying the link
current.Next = prev; // 2. flip
prev = current; // 3. advance prev
current = next; // 4. advance current
}
return prev; // current is null, so prev is the new head
}
}
Always in this order. You may want one tuple line, (current.Next, prev, current) = (prev, current, next). It works in C#, but the order of evaluation is hard to check under pressure. Write the four lines.
public static class TemplateB
{
/// <summary>Reverse the n nodes after before, in place, and restitch both ends.</summary>
/// <param name="before">The node just in front of the block.</param>
/// <param name="n">Block size. At least n nodes must follow before.</param>
/// <example>ReverseN(node 0 of 0 -> 1 -> 2 -> 3, 2) gives 0 -> 2 -> 1 -> 3.</example>
public static void ReverseN(ListNode before, int n)
{
// n < 1: an empty block, so there is nothing to flip or stitch.
if (n < 1) return;
// !: n is at least 1, so the block has a first node.
var tail = before.Next!; // the block's first node becomes its last
ListNode? prev = null; // null: a temporary end. The back joint fixes it.
ListNode? current = tail;
// i counts flips done. Starts at 0, so i < n runs exactly n flips.
// Invariant: the nodes flipped so far are reversed, and prev heads them.
for (int i = 0; i < n; i++)
{
var next = current!.Next; // save the rest before breaking the link
current.Next = prev; // flip this node to point backwards
prev = current; // prev moves up to the node just flipped
current = next; // step forward into the unflipped part
}
before.Next = prev; // front joint: point at the new first node
tail.Next = current; // back joint: old first node now leads the rest
}
}
The two joints at the end are the whole difficulty of every partial reversal. Name them front joint and back joint. Draw them before you code.
Reading the figure. Node 0 is before and node 4 starts the rest of the list. Green circles and arrows are the reversed block. Blue is current. Grey is an old link. Purple arrows are the two new links. Notice that before still points at node 1 after the loop. The front joint fixes that. The back joint stops node 1 from ending the list.
head instead of prev. After a full reversal, head is the last node.current.Next before you save it strands everything after it. Save first, always.! after Next is a promise. Put one only where a comment says why the node exists.Given the head of a singly linked list, reverse it and return the new head.
public static class ReverseLinkedList
{
/// <summary>Reverse a singly linked list in place.</summary>
/// <param name="head">First node, or null for an empty list.</param>
/// <returns>The head of the reversed list, which is the old last node.</returns>
/// <example>Reverse(1 -> 2 -> 3) returns 3 -> 2 -> 1.</example>
public static ListNode? Reverse(ListNode? head)
{
ListNode? prev = null; // null: the old head must end the new list
var current = head; // the next node to flip
// Invariant: everything before current is reversed, headed by prev.
while (current is not null)
{
var next = current.Next; // save the rest before breaking the link
current.Next = prev; // flip this node to point backwards
prev = current; // prev moves up to the node just flipped
current = next; // step forward into the unflipped part
}
return prev; // current is null, so prev is the old last node
}
/// <summary>Same result as a recursion. Reverse the rest, then hang head on its end.</summary>
/// <param name="head">First node, or null for an empty list.</param>
/// <returns>The head of the reversed list.</returns>
/// <example>ReverseRecursive(1 -> 2 -> 3 -> 4) returns 4 -> 3 -> 2 -> 1.</example>
public static ListNode? ReverseRecursive(ListNode? head)
{
// Base case. null is an empty list. A null Next means one node.
if (head?.Next is null)
return head; // empty or single node: already reversed
// Trust the call: it returns the reversed rest, headed by the old last node.
var newHead = ReverseRecursive(head.Next);
// head.Next is now the tail of the reversed rest. Make it point back.
head.Next.Next = head;
head.Next = null; // null: head is now the last node
return newHead; // the same head, passed up every level
}
}
StackOverflowException cannot be caught, so the whole process dies. Say this without being asked. It is real engineering judgement and it lands well.1 → 2 → 3 → null:
prev = null, current = 1. The list reads 1 → 2 → 3.prev = 1, current = 2. Done part 1 → null, rest 2 → 3.prev = 2, current = 3. Done part 2 → 1, rest 3.prev = 3, current = null. The list reads 3 → 2 → 1.current reaches null, prev holds the new head, node 3.Reading the figure. Green nodes and arrows are the reversed part, and prev is its head. The blue node is current. Grey nodes and arrows are not touched yet. Read top to bottom. The green arrows grow from the left while the grey ones shrink, until no grey arrow is left.
prev stays null, which is correct.Next becomes null, and it returns itself.Next must end up null. The first pass does that, because prev starts at null. Point this out.prev, not head. When the loop ends, current is null and prev sits on the last node I flipped.”Reverse the nodes from position left to position right. Positions are 1-indexed and inclusive. Return the head. Do it in one pass.
left, the block, and the suffix after right. Only the block moves. You restitch the two joints.left == 1 needs no special case.left. Call it before. Save before.Next as tail. After the flip, the block’s first node is its last.right - left + 1 times. Then make the two joints.public static class ReverseLinkedListII
{
/// <summary>Reverse the sublist from 1-indexed position left to right, inclusive.</summary>
/// <param name="head">First node.</param>
/// <param name="left">Start position, 1-indexed.</param>
/// <param name="right">End position, 1-indexed, with left <= right <= length.</param>
/// <returns>The head of the changed list.</returns>
/// <example>ReverseBetween(1 -> 2 -> 3 -> 4 -> 5, 2, 4) gives 1 -> 4 -> 3 -> 2 -> 5</example>
public static ListNode? ReverseBetween(ListNode? head, int left, int right)
{
// 1: positions start at 1, so anything lower is a caller bug.
if (left < 1 || right < left)
throw new ArgumentOutOfRangeException(nameof(left), "need 1 <= left <= right");
// Empty list, or a block of one node: nothing to reverse.
if (head is null || left == right)
return head;
// 0: filler value. The dummy gives position 1 a predecessor too.
var dummy = new ListNode(0, head);
// Step 1: walk to the node just before the block.
var before = dummy;
// left - 1 steps: dummy sits at position 0, so this lands on position left - 1.
// Invariant: before sits at position i after i steps.
for (int i = 0; i < left - 1; i++)
before = before.Next!; // !: left <= length, so this node exists
// Step 2: reverse exactly right - left + 1 nodes.
var tail = before.Next!; // first node of the block, the future tail
ListNode? prev = null; // null: temporary end, fixed at the back joint
ListNode? current = tail;
// + 1: both ends are inclusive, so the block has right - left + 1 nodes.
// Invariant: the nodes flipped so far are reversed, and prev heads them.
for (int i = 0; i < right - left + 1; i++)
{
var next = current!.Next; // save the rest before breaking the link
current.Next = prev; // flip this node to point backwards
prev = current; // prev moves up to the node just flipped
current = next; // step forward into the unflipped part
}
// Step 3: the two joints. prev is the block's new head.
// current is the first node after the block, or null.
before.Next = prev;
tail.Next = current;
return dummy.Next; // the real head, even if left was 1
}
}
1 → 2 → 3 → 4 → 5 with left = 2, right = 4:
before is node 1.tail is node 2, prev is node 4, current is node 5. The block reads 4 → 3 → 2.1.Next = 4.2.Next = 5.Result 1 → 4 → 3 → 2 → 5.
1.Next = 4 and 2.Next = 5 put it back in place.Reading the figure. D is the dummy node. Amber marks the block to reverse. Green is the reversed block. Blue is current, the first node after the block. Purple arrows are the two joints. In the middle row, node 1 still points at node 2. That stale link is what the front joint replaces.
left == 1: before stays on the dummy, and dummy.Next hands back the new head. This is exactly why the dummy is there.left == right: guarded and returned untouched.right == n: current ends as null. The back joint then ends the list correctly.left = 1, right = 2: a good quick trace before you say you are done.left < 1 or right < left: throw ArgumentOutOfRangeException. Ask whether the interviewer wants that or a silent return.Reverse the nodes of a list k at a time and return the changed list. If fewer than k nodes remain at the end, leave them as they are. You may change only the links, not the values.
k nodes. A short last group stays as it is.k steps from groupPrev to find kth, the last node of the group. If the walk hits null, the tail is short and you are done.groupNext, not at null. Seed prev = groupNext. Then the loop makes the back joint for free.groupPrev. Grab it before you overwrite groupPrev.Next.public static class ReverseNodesInKGroup
{
/// <summary>Reverse the list in groups of k, leaving a short tail as is.</summary>
/// <param name="head">First node.</param>
/// <param name="k">Group size. Values below 2 leave the list unchanged.</param>
/// <returns>The head of the changed list.</returns>
/// <example>ReverseKGroup(1 -> 2 -> 3 -> 4 -> 5, 2) returns 2 -> 1 -> 4 -> 3 -> 5.</example>
public static ListNode? ReverseKGroup(ListNode? head, int k)
{
// k <= 1: a group of one node (or none) reverses to itself.
if (k <= 1 || head is null)
return head;
// 0: filler value. The dummy gives the first group a predecessor.
var dummy = new ListNode(0, head);
var groupPrev = dummy; // the node just before the group being worked on
// One pass per group. Invariant: everything up to groupPrev is final.
// The loop ends from inside, when fewer than k nodes remain.
while (true)
{
// Look ahead k nodes. If we run out, the tail stays put.
ListNode? kth = groupPrev;
// i counts steps taken. k steps from groupPrev land on the group's last node.
for (int i = 0; i < k; i++)
{
kth = kth.Next;
if (kth is null) // null: fewer than k nodes left
return dummy.Next;
}
var groupNext = kth.Next; // first node after this group, or null
// Reverse the group. Seeding prev with groupNext makes the
// group's old head point at the rest of the list automatically.
ListNode? prev = groupNext;
var current = groupPrev.Next;
// Stop at groupNext: that is where this group ends.
// != on a class with no operator overload compares references.
// Invariant: nodes from groupPrev.Next up to current are flipped onto prev.
while (current != groupNext)
{
var next = current!.Next; // !: the look-ahead proved k nodes exist
current.Next = prev; // flip this node to point backwards
prev = current; // prev moves up to the node just flipped
current = next; // step forward into the unflipped part
}
// groupPrev.Next is still the group's OLD head, now its tail.
var newGroupPrev = groupPrev.Next!;
groupPrev.Next = kth; // front joint: kth is the group's new head
groupPrev = newGroupPrev; // the old head now sits before the next group
}
}
}
prev = groupNextprev starts at null. So the first node flipped ends the list. Here the group sits in the middle. Its first node flipped should point at whatever follows the group. Seeding prev with groupNext does that on the very first pass. The back joint is already correct when the loop ends. That is one less thing to remember and one less place to slip.1 → 2 → 3 → 4 → 5 with k = 2:
kth = node 2, groupNext = node 3.
2 → 1 → 3 → 4 → 5, and groupPrev = node 1.kth = node 4, groupNext = node 5.
2 → 1 → 4 → 3 → 5, and groupPrev = node 3.null after one step.
groupPrev to the group’s new last node.Reading the figure. Each row shows the list in its current link order. Amber is the group about to flip. Green marks groups already flipped and linked. Grey nodes are untouched. The purple label shows groupPrev, the node just before the next group. Notice it lands on node 1, then node 3. Each was the first node of its group before the flip.
Each node is visited at most twice. One look-ahead touches it, and one reversal flips it. So the total is linear despite the nested loops.
k == 1: guarded, returns the list unchanged. Without the guard the loop still works, but it does pointless work.k >= n: the first look-ahead may fail, and the list comes back untouched. If k == n, it is reversed exactly once.k: the short tail keeps its original order. That is the requirement.null. It is a small change but a different code path. Confirm which variant they want before you write anything.prev with the node after the group. So the back joint happens inside the loop, not after it.”prev, advance current.prev. When current reaches null, prev is the new head.current is reversed and headed by prev.That closes the pointer patterns. Pattern 7, Breadth-First Search, moves to trees and graphs. There the state you carry is a whole queue, not two or three references. The shape of the walk is the answer. The Python version of this page is here.