Interview challenge · easy · linked-list, recursion
Merge Two Sorted Lists
El reto
El enunciado va en inglés, igual que en el vídeo.
Given the heads of two sorted linked lists, merge them into one sorted list made by splicing together the nodes of the two lists. Return its head.
Example
list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4
-> 1 -> 1 -> 2 -> 3 -> 4 -> 4Idea: a dummy head and a tail pointer. Keep taking the smaller of the two current nodes and append it to the tail; when one list runs out, attach the rest of the other. Time O(n + m), space O(1).
La solución
# Merge Two Sorted Lists - ayotl.dev
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def merge(a, b):
# dummy head: no special case for 1st
head = tail = Node(0)
while a and b:
# take the smaller node, advance it
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # append leftovers
return head.next
def build(vals):
head = None
for v in reversed(vals):
head = Node(v, head)
return head
n = merge(build([1, 2, 4]),
build([1, 3, 4]))
out = []
while n:
out.append(str(n.val))
n = n.next
print(" -> ".join(out))
$ python3 merge_two_sorted_lists.py
1 -> 1 -> 2 -> 3 -> 4 -> 4