Pointer-based Data Structures — Duplicating Every Node of a Linked List: 25-Comp-A4 Program Design and Data Structures, December 2018, Q7

Question 7: Pointer-based Data Structures — Duplicating Every Node of a Linked List (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A singly linked list of NODEs (int data, struct node *next), possibly empty.

Find. A function that, in place, inserts a copy of every node immediately after the original it copies — so a list of length $n$ becomes a list of length $2n$ with each original value appearing twice in a row.

Approach. Walk the list one original node at a time; at each node, splice a freshly allocated copy in between it and its current next, then advance the walk pointer past the copy just inserted so the loop never revisits (and infinitely re-duplicates) a node it has already handled.

Get the splice order right. For node $A$ with successor $B$, the new node $A'$ must end up between them: $A \to A' \to B$. Because $A'{\to}\text{next}$ is set to $A{\to}\text{next}$ (i.e. $B$) before $A{\to}\text{next}$ is overwritten to point at $A'$, no pointer to $B$ is ever lost.

#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} NODE;

void dupl(NODE *head)
{
    NODE *cur = head;

    while (cur != NULL) {
        NODE *copy = malloc(sizeof(NODE));
        copy->data = cur->data;
        copy->next = cur->next;   /* copy points to what A used to point to */
        cur->next  = copy;        /* A now points to its own copy */

        cur = copy->next;          /* skip past the copy: resume at the NEXT original */
    }
}

Confirm the empty-list case. When head == NULL, the while condition is false immediately and the function returns having done nothing — exactly the required behaviour, with no special-case branch needed.
Trace it on a 3-node list. Starting list $3 \to 7 \to 5 \to \text{NULL}$: at node 3, insert a copy to get $3\to3'\to7\to5$, then advance to the original 7 (skipping $3'$); at node 7, insert a copy to get $3\to3'\to7\to7'\to5$, advance to the original 5; at node 5, insert a copy to get the final list. $$\boxed{3\to3\to7\to7\to5\to5\to\text{NULL}}$$ Because the walk pointer always resumes at the next original node, the loop visits exactly the $n$ original nodes once each, never touching a node it just created.

Question 7 — results
Input list	Output list
(empty)	(empty)
9	9, 9
3, 7, 5	3, 3, 7, 7, 5, 5

Concept & Theory

Topic. In-place singly linked list splicing, and the ordering constraint on pointer updates that a splice always imposes.

Key relations. To insert node $X$ between $A$ and $A{\to}\text{next}$: set $X{\to}\text{next} = A{\to}\text{next}$ first, then $A{\to}\text{next} = X$ — reversing this order loses the rest of the list.

Why this works. The walk pointer is advanced to copy->next, not to cur->next a second time, which is exactly what keeps the traversal to $n$ steps (one per original node) rather than looping forever re-duplicating the copies it just made. This is the same "resume past what you just inserted" discipline needed in any single-pass list-doubling or list-splitting routine.

Common pitfall. Advancing to cur = cur->next instead of cur = copy->next: both expressions currently evaluate to the same node, but the first reads as "move to the copy" only by the coincidence of which field was written last, and is a common source of off-by-one node-skipping bugs if the function is later refactored; writing the two pointer assignments in the wrong order, which drops the remainder of the original list.

Source. Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., ch. 3 (linked lists); Kernighan & Ritchie, The C Programming Language, 2nd ed., §6.5 (self-referential structures).

Question 7 of 9: Pointer-based Data Structures — Duplicating Every Node of a Linked List

Question 7: Pointer-based Data Structures — Duplicating Every Node of a Linked List (20 marks)