101. Build and Serialize a Singly Linked List

Why this mechanism works

A dummy node removes the special case for the first real node. The tail always names the last built node, so each new allocation can be attached in constant time. Serialization follows links rather than assuming that nodes occupy adjacent memory locations.

State and boundaries

dummy.next is the constructed head. tail is the last constructed node; during serialization current is the next unread node.

Protocol

1. Create a dummy and tail.
2. Allocate one node per value and link it after tail.
3. Advance tail.
4. Return dummy.next.
5. Serialize by reading val and following next until None.

Visualization

dummy -> 1 -> 2 -> 3 -> None
         head       tail
return dummy.next, not dummy

Python implementation

from structures import ListNode

def to_linked(values):
    dummy = ListNode()
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next

def to_values(head):
    output = []
    current = head
    while current is not None:
        output.append(current.val)
        current = current.next
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 to_linked: dummy = ListNode()
values=[1, 2, 3]; dummy=N1(val=0,next=None,random=None)

L5 to_linked: tail = dummy
values=[1, 2, 3]; dummy=N1(val=0,next=None,random=None); tail=N1(val=0,next=None,random=None)

L6 to_linked: for value in values:
values=[1, 2, 3]; dummy=N1(val=0,next=None,random=None); tail=N1(val=0,next=None,random=None); value=1

L7 to_linked: tail.next = ListNode(value)
values=[1, 2, 3]; dummy=N1(val=0,next=N2,random=None); tail=N1(val=0,next=N2,random=None); value=1

L8 to_linked: tail = tail.next
values=[1, 2, 3]; dummy=N1(val=0,next=N2,random=None); tail=N2(val=1,next=None,random=None); value=1

L6 to_linked: for value in values:
values=[1, 2, 3]; dummy=N1(val=0,next=N2,random=None); tail=N2(val=1,next=None,random=None); value=2

L7 to_linked: tail.next = ListNode(value)
values=[1, 2, 3]; dummy=N1(val=0,next=N2,random=None); tail=N2(val=1,next=N3,random=None); value=2

L8 to_linked: tail = tail.next
values=[1, 2, 3]; dummy=N1(val=0,next=N2,random=None); tail=N3(val=2,next=None,random=None); value=2

... 7 intermediate state changes omitted ...

L15 to_values: output.append(current.val)
head=N2(val=1,next=N3,random=None); output=[1, 2]; current=N3(val=2,next=N4,random=None)

L16 to_values: current = current.next
head=N2(val=1,next=N3,random=None); output=[1, 2]; current=N4(val=3,next=None,random=None)

L15 to_values: output.append(current.val)
head=N2(val=1,next=N3,random=None); output=[1, 2, 3]; current=N4(val=3,next=None,random=None)

L16 to_values: current = current.next
head=N2(val=1,next=N3,random=None); output=[1, 2, 3]; current=None

L4 to_linked: dummy = ListNode()
values=[]; dummy=N1(val=0,next=None,random=None)

L5 to_linked: tail = dummy
values=[]; dummy=N1(val=0,next=None,random=None); tail=N1(val=0,next=None,random=None)

Why the solution is correct

Each allocation appends exactly the next input value and leaves prior links unchanged. The chain therefore preserves order and contains fresh nodes. Following next visits precisely that construction order until the final None link.

Time and space

O(n) time for building or serialization. Building returns O(n) nodes; serialization returns O(n) values, with O(1) other traversal state.

Common mistakes

Returning the dummy includes an artificial value. Repeatedly searching for the tail makes construction quadratic.

Reasoning card

Transfer exercise

Add a serializer guard that detects a repeated node identity and reports a cycle instead of looping forever.