Merging and Reordering Lists
Merging and reordering lists is the task of combining two sorted linked lists into one sorted list and rearranging a single list into a new order. Both jobs relink existing nodes instead of building new values.
The recognition signal
A problem asks for merging when it names two sorted lists. A problem asks for reordering when it names a new order for one list.
questions = [
"Merge two sorted lists into one sorted list.",
"Reorder a list so the ends move toward the center.",
]
for q in questions:
print("Signal: " + q)The merge template
The tail pointer takes the smaller head node each round. When one list runs out, the tail takes the rest of the other list.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def merge(a, b):
dummy = Node(0)
tail = dummy
while a is not None and b is not None:
if a.value <= b.value:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a is not None else b
return dummy.next
merged = merge(build([1, 3, 5]), build([2, 4, 6]))
print(to_list(merged))Worked problem: reorder four nodes
The list 1, 2, 3, 4 splits into 1, 2 and 3, 4. The second half reverses to 4, 3, and weaving gives 1, 4, 2, 3.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def reorder(head):
slow = head
fast = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
prev = None
while second is not None:
nxt = second.next
second.next = prev
prev = second
second = nxt
first = head
second = prev
while second is not None:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
return head
print(to_list(reorder(build([1, 2, 3, 4]))))Example
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def reorder(head):
slow = head
fast = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
prev = None
while second is not None:
nxt = second.next
second.next = prev
prev = second
second = nxt
first = head
second = prev
while second is not None:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
return head
print(to_list(reorder(build([1, 2, 3, 4, 5, 6]))))Key points
- A merged list keeps the sorted order of both input lists.
- Use a dummy node to hold the start of the merged list while it is built.
- Use a tail pointer to attach the next smallest node each round.
- Reordering splits a list at the middle, reverses the second half, and weaves the halves together.
- Merging and reordering are both relinking jobs, one across two lists and one inside a single list.
The list splits into 1, 2, 3 and 4, 5, 6. The second half reverses to 6, 5, 4. Weaving the halves together gives 1, 6, 2, 5, 3, 4.
Note
relinking nodes reuses the original nodes, so no new values are created.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Two sorted lists are 1, 5 and 2, 3, 4. What is the merged order?