Insertion, Deletion and Reversal

Insertion, Deletion and Reversal — Tech Epitome

Reversal

Three references, one pass

Input1 → 2 → 3 → null

prev=null cur=1save 2, point 1 at null
prev=1 cur=2save 3, point 2 at 1
prev=2 cur=3save null, point 3 at 2
cur=nullprev is the new head

Result3 → 2 → 1 → null

python

1def reverse(head):2    prev = None3    node = head4    while node is not None:5        nxt = node.next     # save BEFORE overwriting6        node.next = prev7        prev = node8        node = nxt9    return prev             # not head: head is now the tail

Iterative reversal

The dummy head

Operations that might affect the first node otherwise need a branch for it. A throwaway node in front removes that asymmetry entirely.

python

1def remove_value(head, target):2    dummy = ListNode(0, head)   # now nothing is special about the first node3    prev = dummy4    while prev.next is not None:5        if prev.next.val == target:6            prev.next = prev.next.next   # unlink7        else:8            prev = prev.next9    return dummy.next

No special case for the head

Practise

Quick quiz

Linked lists

1What does this reversal return?

def reverse(head):
    prev = None
    node = head
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return head

The correctly reversed list

A single node — the original head, now the tail

None

The original list, unchanged

2What problem does a dummy head node solve?

It makes the list circular

It removes the special case for operations affecting the first node

It speeds up traversal

It stores the list length

3In Floyd's cycle detection you should compare the two pointers by value.

True

False