19

19 — Practice solutions

← Questions

These are independently written explanations, not an official marking scheme.

19A

def to_list(head):
    result = []
    current = head
    while current is not None:
        result.append(current.data)
        current = current.next  # Follow the link; do not change the node's next.
    return result

The final node has next=None but still has data to visit. An empty head has no .next attribute. Test whether a current node exists, then process it.

Reasoning

The traversal processes a node when the node exists, including the final node whose next is None. Advancing a local current reference preserves head and the links. This satisfies the non-mutating requirement.

19B

Requires the Node class from the chapter.

def sorted_insert(head, value):
    new = Node(value)
    previous = None
    current = head
    while current is not None and current.data < value:  # Stop before equals.
        previous = current
        current = current.next
    new.next = current  # Attach the remainder before redirecting its entry link.
    if previous is None:
        return new
    previous.next = new
    return head

The traversal stops on the first equal-or-greater value or at the end. Connecting new.next first preserves the remaining chain. Empty input returns the new node as head.

Reasoning

Inserting before equals means traversal should continue only while values are strictly smaller. Retain the predecessor because a singly linked current node cannot point backwards. At stopping, new must point to current; either head or previous.next must point to new.

19C

Set new15.next to node 20, then node 10.next to new15. To delete node 30, set node 20.next to None. A singly linked node lacks a backward link, so keeping the predecessor during traversal lets us bypass the target without restarting the search.

Reasoning

Only the links bordering the insertion/removal need changing. Rebuilding the entire list is unnecessary. For deletion of 30,20 is the predecessor even after 15 is inserted between10 and 20.

19D

def insert_at(head, position, value):
    if position < 0:
        raise IndexError("invalid position")
    if position == 0:
        return Node(value, head)
    previous = head
    for step in range(position - 1):
        if previous is None:
            raise IndexError("invalid position")
        previous = previous.next
    if previous is None:
        raise IndexError("invalid position")
    previous.next = Node(value, previous.next)
    return head

Input chain / position / value	Expected chain
empty / 0 / 10	10
10 → 20 / 0 / 5	5 → 10 → 20
10 → 20 / 1 / 15	10 → 15 → 20
10 → 20 / 2 / 30	10 → 20 → 30
10 → 20 / 3 / 30	IndexError; original links unchanged

The new node saves the successor before the predecessor link is replaced. Retain the returned head in the caller.

19E

def linked_length(head):
    count = 0
    current = head
    while current is not None:
        count += 1
        current = current.next
    return count
 
def find_first(head, target):
    index = 0
    current = head
    while current is not None:
        if current.data == target:
            return index
        current = current.next
        index += 1
    return -1

Empty list: length 0, lookup −1. For 4 → 7 → 7, length 3 and lookup of 7 returns 1. Local traversal pointers leave the structure unchanged.