Interview challenge · easy · linked-list, recursion

Reverse Linked List

The challenge

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

Example

1 -> 2 -> 3 -> 4 -> 5   ->   5 -> 4 -> 3 -> 2 -> 1

Idea: walk the list once with three pointers: prev, the current node and the saved next. Point each node back to prev, then step forward. Time O(n), space O(1).

The solution

1# Reverse Linked List - ayotl.dev
2class Node:
3    def __init__(self, val, next=None):
4        self.val, self.next = val, next
5
6
7def reverse(head):
8    prev = None
9    while head:
10        nxt = head.next   # save the rest
11        head.next = prev  # point backwards
12        prev, head = head, nxt
13    return prev  # old tail is the new head
14
15
16head = None
17for v in [5, 4, 3, 2, 1]:
18    head = Node(v, head)
19
20node, out = reverse(head), []
21while node:
22    out.append(str(node.val))
23    node = node.next
24print(" -> ".join(out))

$ python3 reverse_linked_list.py

5 -> 4 -> 3 -> 2 -> 1

The video

Watch on YouTube →