Interview challenge · easy · linked-list, recursion
Reverse Linked List
El reto
El enunciado va en inglés, igual que en el vídeo.
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 -> 1Idea: 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).
La solución
# Reverse Linked List - ayotl.dev
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def reverse(head):
prev = None
while head:
nxt = head.next # save the rest
head.next = prev # point backwards
prev, head = head, nxt
return prev # old tail is the new head
head = None
for v in [5, 4, 3, 2, 1]:
head = Node(v, head)
node, out = reverse(head), []
while node:
out.append(str(node.val))
node = node.next
print(" -> ".join(out))
$ python3 reverse_linked_list.py
5 -> 4 -> 3 -> 2 -> 1