Linked Lists Checkpoint

Optional

28 min · Intermediate

A review of this module. Skip it if you feel confident; the next module does not need it.

Fix the mistakes

The slips that cost marks in this module. Spot each one, then check the fix.

This checkpoint mixes everything in the module. Decide first which technique fits the clue, then write the loop and trace it on a short list.

Walk and rewire with a dummy node

When a problem changes which nodes stay, put a dummy node before the head. Walk with node, and look one step ahead at node.next so you can skip it.

Python

1def remove_below(head, low):2    dummy = Node(0, head)3    node = dummy4    while node.next:5        if node.next.value < low:6            node.next = node.next.next7        else:8            node = node.next9    return dummy.next

Example 1 · Keep passing marks

Python

1class Node:2    def __init__(self, value, next=None):3        self.value = value4        self.next = next5
6
7def build(values):8    head = None9    for value in reversed(values):10        head = Node(value, head)11    return head12
13
14def to_list(head):15    out = []16    node = head17    while node:18        out.append(node.value)19        node = node.next20    return out21
22
23def remove_below(head, low):24    dummy = Node(0, head)25    node = dummy26    while node.next:27        if node.next.value < low:28            node.next = node.next.next29        else:30            node = node.next31    return dummy.next32
33
34print(to_list(remove_below(build([35, 82, 40, 91, 28]), 40)))

Output

[82, 40, 91]

What this code does

Marks below 40 are skipped, including the head 35. The dummy node handles the head without extra code.
The remaining nodes keep their order.

Return dummy.next, not head: the head may be gone. Move node only when nothing was removed. Time is O(n) and space is O(1).

Two pointers: a gap or two speeds

Two pointers a fixed gap apart find a node counted from the end. Two pointers at different speeds find the middle or a cycle. Both need one pass and no extra memory.

Python

1def kth_from_end(head, k):2    lead = trail = head3    for _ in range(k):4        lead = lead.next5    while lead:6        lead = lead.next7        trail = trail.next8    return trail.value

Example 2 · Value third from the end

Python

1class Node:2    def __init__(self, value, next=None):3        self.value = value4        self.next = next5
6
7def build(values):8    head = None9    for value in reversed(values):10        head = Node(value, head)11    return head12
13
14def kth_from_end(head, k):15    lead = trail = head16    for _ in range(k):17        lead = lead.next18    while lead:19        lead = lead.next20        trail = trail.next21    return trail.value22
23
24head = build([10, 20, 30, 40, 50, 60])25print(kth_from_end(head, 3), kth_from_end(head, 1))

Output

40 60

What this code does

The 3rd from the end of six nodes is 40, and the 1st from the end is the last node, 60.
One pass and O(1) space: no length is counted.

After k steps, lead is k nodes ahead. When it walks off the end, trail stands on the k-th node from the end.

Choose the technique from the clue

A change at the head, or removing nodes, points to a dummy node. The middle, a cycle or a count from the end points to two pointers. Reversing, or comparing the ends, points to in-place reversal.

Example 3 · Group odd and even positions

Python

1class Node:2    def __init__(self, value, next=None):3        self.value = value4        self.next = next5
6
7def build(values):8    head = None9    for value in reversed(values):10        head = Node(value, head)11    return head12
13
14def to_list(head):15    out = []16    node = head17    while node:18        out.append(node.value)19        node = node.next20    return out21
22
23def odd_even(head):24    if head is None:25        return None26    odd, even = head, head.next27    even_head = even28    while even and even.next:29        odd.next = even.next30        odd = odd.next31        even.next = odd.next32        even = even.next33    odd.next = even_head34    return head35
36
37print(to_list(odd_even(build([1, 2, 3, 4, 5, 6]))))38print(to_list(odd_even(build([1, 2, 3, 4, 5]))))

Output

[1, 3, 5, 2, 4, 6]
[1, 3, 5, 2, 4]

What this code does

Nodes in positions 1, 3, 5 come first, then those in positions 2, 4, 6. Order inside each group is kept.
Only links change, so it is O(n) time and O(1) space.

Module quiz

Questions from the whole module. Your first answer is your score.

Problems

Graded easy to hard, using everything from this module.

Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.

Exercise 1· Easy

Remove all nodes holding an even number from [1, 2, 3, 4, 5, 6] and print the rest.

Expected output

1 3 5

Exercise 2· Easy

Print the sum of all values in the list [12, 8, 20, 5] by walking the nodes.

Expected output

Exercise 3· Easy

Insert 6 at the front of [7, 8, 9] and append 10 at the end. Print the list.

Expected output

6 7 8 9 10

Exercise 4· Medium

Print the middle value of [3, 6, 9, 12, 15, 18, 21].

Expected output

Exercise 5· Medium

Print the list [5, 4, 3, 2, 1] reversed, as values separated by spaces.

Expected output

1 2 3 4 5

Exercise 6· Medium

Print the value that is 2nd from the end in [11, 22, 33, 44, 55] using two pointers.

Expected output

Exercise 7· Hard

Merge [2, 6, 10] and [1, 7] (both sorted) and print the merged list.

Expected output

1 2 6 7 10

Exercise 8· Hard

Print YES if [2, 5, 9, 5, 2] is a palindrome list and NO otherwise. Do not copy the values to a list.

Expected output

YES

Interview questions

Questions interviewers ask on this topic.

Finish up

Mark complete & continue

Next: Must-do problems: Linked Lists

1def remove_below(head, low):2 dummy = Node(0, head)3 node = dummy4 while node.next:5 if node.next.value < low:6 node.next = node.next.next7 else:8 node = node.next9 return dummy.next

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7def build(values):8 head = None9 for value in reversed(values):10 head = Node(value, head)11 return head12 13 14def to_list(head):15 out = []16 node = head17 while node:18 out.append(node.value)19 node = node.next20 return out21 22 23def remove_below(head, low):24 dummy = Node(0, head)25 node = dummy26 while node.next:27 if node.next.value < low:28 node.next = node.next.next29 else:30 node = node.next31 return dummy.next32 33 34print(to_list(remove_below(build([35, 82, 40, 91, 28]), 40)))

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7def build(values):8 head = None9 for value in reversed(values):10 head = Node(value, head)11 return head12 13 14def kth_from_end(head, k):15 lead = trail = head16 for _ in range(k):17 lead = lead.next18 while lead:19 lead = lead.next20 trail = trail.next21 return trail.value22 23 24head = build([10, 20, 30, 40, 50, 60])25print(kth_from_end(head, 3), kth_from_end(head, 1))

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7def build(values):8 head = None9 for value in reversed(values):10 head = Node(value, head)11 return head12 13 14def to_list(head):15 out = []16 node = head17 while node:18 out.append(node.value)19 node = node.next20 return out21 22 23def odd_even(head):24 if head is None:25 return None26 odd, even = head, head.next27 even_head = even28 while even and even.next:29 odd.next = even.next30 odd = odd.next31 even.next = odd.next32 even = even.next33 odd.next = even_head34 return head35 36 37print(to_list(odd_even(build([1, 2, 3, 4, 5, 6]))))38print(to_list(odd_even(build([1, 2, 3, 4, 5]))))

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7head = Node(1, Node(2, Node(3, Node(4))))8node = head9while node.next:10 node = node.next11print(node.value, head.value)

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7def reverse(head):8 prev = None9 node = head10 while node:11 nxt = node.next12 node.next = prev13 prev = node14 node = nxt15 return prev16 17 18head = reverse(Node(1, Node(2, Node(3))))19out = []20while head:21 out.append(head.value)22 head = head.next23print(*out)

1class Node:2 def __init__(self, value, next=None):3 self.value = value4 self.next = next5 6 7def merge(a, b):8 dummy = tail = Node(0)9 while a and b:10 if a.value <= b.value:11 tail.next, a = a, a.next12 else:13 tail.next, b = b, b.next14 tail = tail.next15 tail.next = a or b16 return dummy.next17 18 19def to_list(head):20 out = []21 while head:22 out.append(head.value)23 head = head.next24 return out25 26 27print(to_list(merge(Node(1, Node(3)), Node(2, Node(4)))))

Walk and rewire with a dummy node

What this code does

Two pointers: a gap or two speeds

What this code does

Choose the technique from the clue

What this code does

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Walk and rewire with a dummy node

What this code does

Two pointers: a gap or two speeds

What this code does

Choose the technique from the clue

What this code does

Why return dummy.next and not head after removing nodes?

What does this print?

What does it cost to reach the 100th node of a linked list?

Which tool is built into Python for fast adds and removes at both ends?

What does node.next = node.next.next do?

What is the cost of inserting a node after a node you already hold?

What does this print?

After node.next = prev in a reverse loop, what would be lost without a saved nxt?

For a 7-node list, which node do slow and fast pointers leave slow on?

What does slow is fast mean for a list walk?

How can you find the 2nd node from the end in one pass?

What does this print?

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Q1When is a linked list better than a Python list?

Q2How do you choose between a dummy node and two pointers?

Q3Walk through detecting a cycle and finding where it starts.

Q4What are the usual edge cases in linked list problems?

Q5Why is reversing a list in place O(1) space?

Why return dummy.next and not head after removing nodes?

What does this print?

What does it cost to reach the 100th node of a linked list?

Which tool is built into Python for fast adds and removes at both ends?

What does node.next = node.next.next do?

What is the cost of inserting a node after a node you already hold?

What does this print?

After node.next = prev in a reverse loop, what would be lost without a saved nxt?

For a 7-node list, which node do slow and fast pointers leave slow on?

What does slow is fast mean for a list walk?

How can you find the 2nd node from the end in one pass?

What does this print?

Q1When is a linked list better than a Python list?

Q2How do you choose between a dummy node and two pointers?

Q3Walk through detecting a cycle and finding where it starts.

Q4What are the usual edge cases in linked list problems?

Q5Why is reversing a list in place O(1) space?

Why return `dummy.next` and not `head` after removing nodes?

What does `node.next = node.next.next` do?

After `node.next = prev` in a reverse loop, what would be lost without a saved `nxt`?

For a 7-node list, which node do slow and fast pointers leave `slow` on?

What does `slow is fast` mean for a list walk?

Why return `dummy.next` and not `head` after removing nodes?

What does `node.next = node.next.next` do?

After `node.next = prev` in a reverse loop, what would be lost without a saved `nxt`?

For a 7-node list, which node do slow and fast pointers leave `slow` on?

What does `slow is fast` mean for a list walk?