mycsmajor
Data structures problem 13 of 30

Reverse a linked list

  • Data structures
  • Medium

Given the head of a singly linked list, reverse the list in place and return the new head.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

# 1 -> 2 -> 3 -> None
# becomes
# 3 -> 2 -> 1 -> None
Show hint

Walk the list once, keeping track of the previous node. Before you repoint node.next, save where you were going.

Show solution 
def reverse(head):
    prev = None
    node = head
    while node:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return prev

Each step flips one arrow to point backwards. nxt stops you from losing the rest of the list. When node runs off the end, prev is the old tail, which is the new head. O(n) time, O(1) extra space.

Want a problem like this every day? See today's problem and keep a streak going.