Start learning free

LESSON 276 OF 347 · LINKED LISTS

Reverse Linked List in C#: O(n) Time and O(1) Space by Flipping Links

Practice O(n) Read the full explanation

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

Example:

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


Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

This problem is avery similar to "Reverse String" problem, so it's natural to think of adapting that solution for Linked Lists. Unfortunately, traversing with two pointers doesn't work here because the right pointer should move to the left, and we cannot do that in a Linked List. The trick is actually in modifying the links of our Linked List to obtain its reversed version. How should we modify them?

We just have to reverse each link in the list. For example: 1 -> 2 -> 3 -> 4 should become 1 <- 2 <- 3 <- 4. And the head of the reversed list is the tail of the original one. How can we reverse these links?

One idea is to traverse the list from left to right using a variable node and convert each link node -> node.next to node.next -> node: 
node = head
while node:
  nextNode = node.next
  nextNode.next = node
  node = nextNode
But there is a problem with this algorithm. Can you find out what that is? Take some small example and run it by hand.

The problem is that the moment we reverse a link, we lose access to the next nodes. For example, if the list is 1 -> 2 -> 3. When node is 1, we reverse the link and the list becomes 1 <- 2 3. We lost the link between 2 and 3. And so at the next step node becomes 2 but node.next is 1 instead of 3. The solution is still good, but we need to implement it in such a way that this problem is fixed.

We should traverse the linked list, while using two pointers:
  • prev - the previous node
  • node - the current node
We will start with the first two nodes in the list: prev = head and node = head.next Then, for as long as node != NULL, we will reverse the link prev -> node and update the two variables such that they point to the next two nodes. Can you figure out how to code this? Take the example above and figure out how you should update the pointers after each link reversal. 

prev = head
node = head.next
while node:
  	nextNode = node.next
	node.next = prev
	prev = node
	node = nextNode


STEP 1 OF 9
    Ctrl + Enter to check

    C# · LINKED LISTS

    Reverse Linked List in C#, explained

    Problem overview

    The method Reverse receives the head of a singly linked list and returns the head of the reversed list. For [1, 2, 3, 4, 5] it returns [5, 4, 3, 2, 1]. The nodes are ListNode objects with an int val and a ListNode next reference.

    The lesson asks for O(n) time and O(1) extra space. That rules out copying the values into an array or a List<int> and rebuilding the list. The nodes themselves have to be rewired.

    Approach: reverse each link in place

    Reversing a list means that every link a -> b becomes b -> a, and that the old last node becomes the head. The idea is to walk the list once from left to right and flip one link per step.

    The danger is losing the way forward. Suppose that while standing on node 2 of 1 -> 2 -> 3 you write node.next = prev right away. Node 2 now points back at node 1, and nothing refers to node 3 any more, so the walk cannot continue. The fix is to save the next node before changing the link, and to remember the previous node so that the current one has something to point back to. The same idea works for a list of any length, because each step only needs its immediate neighbors.

    That gives three pointers during the loop:

    • prev: the node before the current one, which the current node will point back to.
    • node: the node whose link is being flipped.
    • nextNode: the saved rest of the list.

    Tracing 1 -> 2 -> 3:

    1. Setup: prev is node 1, node is node 2, and node 1's next is cut to null. The list is now null <- 1 and 2 -> 3.
    2. First pass: save node 3, make 2 point to 1, move prev to 2 and node to 3. Now null <- 1 <- 2 and 3 remains.
    3. Second pass: save null, make 3 point to 2, move prev to 3 and node to null.
    4. The loop stops. prev is node 3, the head of 3 -> 2 -> 1.

    Step by step

    1. Declare prev as a ListNode and start it at head. The original head will become the last node.
    2. Declare node and start it at head.next, the second node, because the head is handled separately.
    3. Cut the head's link with head.next = null. If the head kept pointing at the second node, the reversed list would end in a cycle between the first two nodes.
    4. Loop while node != null.
    5. Save the rest in nextNode = node.next before changing any link.
    6. Flip the link: node.next = prev.
    7. Move prev forward to node.
    8. Move node forward to nextNode. The order of steps 7 and 8 matters: prev takes the current node first, and only then does node move on.
    9. Return prev. When node becomes null, prev holds the last node processed, which is the new head.

    The solution in C#

    class Solution {
    public ListNode Reverse(ListNode head) {
        ListNode prev = head;
        ListNode node = head.next;
        head.next = null;
        while (node != null) {
            ListNode nextNode = node.next;
            node.next = prev;
            prev = node;
            node = nextNode;
        }
        return prev;
    }
}

    C# details worth knowing

    • References, not copies. ListNode is a class, so prev = node copies a reference, and both variables now refer to the same node. Nothing is duplicated, which is why the method needs no extra memory.
    • Declaring inside the loop. ListNode nextNode is declared on each pass, and its scope ends with the loop body. It is only a reference, so there is no cost.
    • The argument is modified. The method rewires the caller's nodes. After the call, the original head variable still refers to the first node, which is now the last, and its next is null.
    • Null handling. Reading head.next when head is null throws NullReferenceException. This solution assumes the list has at least one node. An empty list would need a guard such as if (head == null) return null; before the first line.

    Complexity

    The loop visits each node once and does a constant amount of work, so the time is O(n). Only three references are kept beyond the list itself, so the extra space is O(1). There is no recursion, so the call stack does not grow with the list length.

    Edge cases and common mistakes

    • A single node. node starts as null, the loop never runs, and prev is the head itself, so the result is the same one-node list.
    • Two nodes. 1 -> 2 becomes 2 -> 1. The loop runs once.
    • Not saving node.next. If you assign node.next = prev first, the rest of the list is lost and the loop ends early.
    • Forgetting head.next = null. The old head would still point at the second node, and the new tail would point back into the list, which creates a cycle.
    • Returning head. After reversing, the original head is the tail. The new head is prev.
    • Updating in the wrong order. Setting node = nextNode before prev = node would move prev to the wrong node.

    Testing

    Results from running the solution:

    • [1, 2, 3, 4, 5] returns [5, 4, 3, 2, 1].
    • [1, 2] returns [2, 1].
    • [1] returns [1].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free