← Linked Lists

Select a question from the sidebar

15 questions in this topic

Question 1 / 15

How do you define a singly linked list node structure in C?

A singly linked list node is a self-referential structure containing data and a pointer to the next node. The struct Node uses a pointer to its own type to create the chain.

Key design decisions:

Use typedef to avoid writing struct Node everywhere
The next pointer is NULL for the last node in the list
You must use struct Node *next inside the definition (not the typedef alias) because the typedef is not yet complete

Memory layout: Each node occupies sizeof(int) + sizeof(pointer) bytes, typically 8 or 12 bytes on 32-bit systems, 12 or 16 bytes on 64-bit systems due to alignment/padding.

Pseudo Code

Define struct Node:
  int data
  pointer to struct Node -> next

Create node:
  Allocate memory for one Node
  Set data = value
  Set next = NULL
  Return pointer to node

Code

#include <stdio.h>
#include <stdlib.h>

/* Self-referential structure for singly linked list */
typedef struct Node {
    int data;
    struct Node *next;  /* pointer to next node */
} Node;

/* Factory function to create a new node */
Node *createNode(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main(void) {
    Node *head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);

    /* Traverse and print */
    Node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");  /* Output: 10 -> 20 -> 30 -> NULL */

    /* Free all nodes */
    curr = head;
    while (curr != NULL) {
        Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    return 0;
}

Key Points

•Self-referential struct: contains a pointer to its own type
•Use struct Node *next inside the definition, not the typedef alias
•Always check malloc return value for NULL
•Last node's next pointer is NULL (sentinel for end of list)
•sizeof(Node) includes padding for alignment

Gotchas

•Cannot use the typedef name inside the struct definition itself -- use struct Node *next, not Node *next
•Forgetting to set next = NULL in createNode leads to undefined behavior when traversing
•Forgetting to check malloc return can cause NULL pointer dereference
•sizeof(Node) may be larger than sizeof(int) + sizeof(Node*) due to struct padding

A linked list node is a self-referential struct with data and a next pointer. Use malloc to allocate each node and always set next = NULL for the tail.

•Self-referential struct with data + next pointer
•Always initialize next to NULL

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

Must use struct Node *next inside the definition, not the typedef alias

Question 2 / 15

How do you insert nodes at the head, tail, and a given position in a singly linked list?

Linked list insertion has three variants:

Insert at head (O(1)): Create new node, point its next to current head, update head pointer. This is the fastest insertion.

Insert at tail (O(n)): Traverse to the last node, set its next to the new node. Can be made O(1) if you maintain a tail pointer.

Insert at position k (O(k)): Traverse to position k-1, set new node's next to position k node, set position k-1 node's next to new node.

Critical: When inserting at the head, you must update the head pointer. This is why many implementations pass Node **head (pointer to pointer) so the function can modify the caller's head variable.

Pseudo Code

InsertAtHead(head, value):
  new = createNode(value)
  new->next = *head
  *head = new

InsertAtTail(head, value):
  new = createNode(value)
  if *head is NULL:
    *head = new
    return
  curr = *head
  while curr->next != NULL:
    curr = curr->next
  curr->next = new

InsertAtPosition(head, value, pos):
  if pos == 0: InsertAtHead(head, value)
  curr = *head
  for i = 0 to pos-2:
    curr = curr->next
  new = createNode(value)
  new->next = curr->next
  curr->next = new

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(1); }
    n->data = val;
    n->next = NULL;
    return n;
}

/* Insert at head: O(1) */
void insertAtHead(Node **head, int val) {
    Node *newNode = createNode(val);
    newNode->next = *head;
    *head = newNode;
}

/* Insert at tail: O(n) */
void insertAtTail(Node **head, int val) {
    Node *newNode = createNode(val);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *curr = *head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = newNode;
}

/* Insert at position (0-indexed): O(pos) */
void insertAtPosition(Node **head, int val, int pos) {
    if (pos == 0) {
        insertAtHead(head, val);
        return;
    }
    Node *curr = *head;
    for (int i = 0; i < pos - 1 && curr != NULL; i++)
        curr = curr->next;
    if (curr == NULL) {
        fprintf(stderr, "Position out of range\n");
        return;
    }
    Node *newNode = createNode(val);
    newNode->next = curr->next;
    curr->next = newNode;
}

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    Node *head = NULL;
    insertAtTail(&head, 10);
    insertAtTail(&head, 30);
    insertAtHead(&head, 5);
    insertAtPosition(&head, 20, 2);
    printList(head);  /* 5 -> 10 -> 20 -> 30 -> NULL */
    return 0;
}

5 -> 10 -> 20 -> 30 -> NULL

Key Points

•Use Node **head (double pointer) to modify the head from inside a function
•Insert at head is O(1), insert at tail is O(n) without a tail pointer
•Insert at position requires traversing to pos-1 first
•Always handle the empty list case (head == NULL)
•Order of pointer updates matters: set new->next before changing prev->next

Gotchas

•Passing Node *head instead of Node **head means the caller's head never changes
•Inserting at position beyond the list length can dereference NULL
•Forgetting to handle the empty list case causes segfault on tail insertion
•Must set new->next before overwriting curr->next or you lose the rest of the list

Use Node **head (double pointer) to modify head from a function. Insert at head: O(1) -- point new node to old head, update head. Insert at tail: O(n) -- traverse to end. Insert at position: traverse to pos-1, splice in.

•Double pointer (Node **head) needed to modify head
•Head insert O(1), tail insert O(n)

void insertAtHead(Node **head, int val) {
    Node *n = createNode(val);
    n->next = *head;
    *head = n;
}

void insertAtTail(Node **head, int val) {
    Node *n = createNode(val);
    if (!*head) { *head = n; return; }
    Node *c = *head;
    while (c->next) c = c->next;
    c->next = n;
}

Passing Node *head instead of Node **head won't update the caller's head pointer

Question 3 / 15

How do you delete nodes from a singly linked list by value and by position?

Deleting from a linked list involves finding the target node, relinking the previous node's next pointer to skip the target, and freeing the target's memory.

Delete by value: Traverse until you find the node whose data matches. Keep track of the previous node so you can relink.

Delete by position: Traverse to position-1, relink, free the target.

Special case -- deleting head: The head pointer itself must change. This is why we use Node **head.

Steps:

Handle empty list
Handle deletion of head node (special case)
Traverse to find target, keeping track of previous
Relink: prev->next = target->next
free(target)

Pseudo Code

DeleteByValue(head, value):
  if *head is NULL: return
  if (*head)->data == value:
    temp = *head
    *head = (*head)->next
    free(temp)
    return
  curr = *head
  while curr->next != NULL and curr->next->data != value:
    curr = curr->next
  if curr->next != NULL:
    temp = curr->next
    curr->next = temp->next
    free(temp)

DeleteByPosition(head, pos):
  if pos == 0: delete head node
  traverse to pos-1
  relink and free

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Delete first occurrence of value */
void deleteByValue(Node **head, int val) {
    if (*head == NULL) return;

    /* Special case: deleting the head */
    if ((*head)->data == val) {
        Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    Node *curr = *head;
    while (curr->next != NULL && curr->next->data != val)
        curr = curr->next;

    if (curr->next != NULL) {
        Node *temp = curr->next;
        curr->next = temp->next;
        free(temp);
    }
}

/* Delete node at 0-indexed position */
void deleteByPosition(Node **head, int pos) {
    if (*head == NULL) return;

    if (pos == 0) {
        Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    Node *curr = *head;
    for (int i = 0; i < pos - 1 && curr->next != NULL; i++)
        curr = curr->next;

    if (curr->next == NULL) return;  /* position out of range */

    Node *temp = curr->next;
    curr->next = temp->next;
    free(temp);
}

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    Node *head = NULL;
    for (int i = 1; i <= 5; i++) {
        Node *n = createNode(i * 10);
        n->next = head;
        head = n;
    }
    printList(head);        /* 50 -> 40 -> 30 -> 20 -> 10 -> NULL */

    deleteByValue(&head, 30);
    printList(head);        /* 50 -> 40 -> 20 -> 10 -> NULL */

    deleteByPosition(&head, 0);
    printList(head);        /* 40 -> 20 -> 10 -> NULL */

    deleteByPosition(&head, 1);
    printList(head);        /* 40 -> 10 -> NULL */
    return 0;
}

50 -> 40 -> 30 -> 20 -> 10 -> NULL
50 -> 40 -> 20 -> 10 -> NULL
40 -> 20 -> 10 -> NULL
40 -> 10 -> NULL

Key Points

•Always handle empty list and head-deletion as special cases
•Keep a pointer to the previous node to relink around the deleted node
•free() the deleted node to avoid memory leaks
•Use Node **head so the function can update the caller's head pointer
•Check bounds before accessing curr->next

Gotchas

•Forgetting to free the deleted node causes a memory leak
•Using the freed pointer after free() is undefined behavior (use-after-free)
•Deleting the head without updating the head pointer leaves a dangling pointer
•Not handling the case where the value is not found can cause a segfault

To delete: find the node before the target, relink prev->next = target->next, then free(target). Handle head deletion separately since the head pointer must change.

•Relink prev->next to skip the deleted node, then free it
•Handle head deletion as a special case

void deleteByValue(Node **head, int val) {
    if (!*head) return;
    if ((*head)->data == val) {
        Node *tmp = *head;
        *head = (*head)->next;
        free(tmp);
        return;
    }
    Node *c = *head;
    while (c->next && c->next->data != val)
        c = c->next;
    if (c->next) {
        Node *tmp = c->next;
        c->next = tmp->next;
        free(tmp);
    }
}

Forgetting free() causes memory leaks; using a freed pointer is undefined behavior

Question 4 / 15

How do you traverse and print all elements of a singly linked list?

Traversal is the fundamental linked list operation. Start at the head and follow next pointers until you reach NULL.

Iterative traversal: Use a curr pointer starting at head. In each iteration, process the current node and advance: curr = curr->next. Stop when curr == NULL.

Recursive traversal: Call the function on node->next until the base case (node == NULL). Useful for reverse printing (print after the recursive call).

Common traversal tasks:

Print all elements
Count nodes (list length)
Search for a value
Find the last node

Time complexity: O(n) for all traversals. Space: O(1) iterative, O(n) recursive (call stack).

Pseudo Code

IterativeTraversal(head):
  curr = head
  while curr != NULL:
    process(curr->data)
    curr = curr->next

RecursiveTraversal(node):
  if node is NULL: return
  process(node->data)
  RecursiveTraversal(node->next)

CountNodes(head):
  count = 0
  curr = head
  while curr != NULL:
    count++
    curr = curr->next
  return count

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Iterative print */
void printList(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

/* Recursive print */
void printListRecursive(Node *node) {
    if (node == NULL) {
        printf("NULL\n");
        return;
    }
    printf("%d -> ", node->data);
    printListRecursive(node->next);
}

/* Reverse print using recursion (print after recursive call) */
void printReverse(Node *node) {
    if (node == NULL) return;
    printReverse(node->next);
    printf("%d ", node->data);
}

/* Count nodes */
int countNodes(Node *head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head->next;
    }
    return count;
}

/* Search for a value, return 1 if found, 0 otherwise */
int search(Node *head, int target) {
    while (head != NULL) {
        if (head->data == target)
            return 1;
        head = head->next;
    }
    return 0;
}

int main(void) {
    Node n3 = {30, NULL};
    Node n2 = {20, &n3};
    Node n1 = {10, &n2};

    printList(&n1);           /* 10 -> 20 -> 30 -> NULL */
    printListRecursive(&n1);  /* 10 -> 20 -> 30 -> NULL */

    printf("Reverse: ");
    printReverse(&n1);        /* 30 20 10 */
    printf("\n");

    printf("Count: %d\n", countNodes(&n1));  /* 3 */
    printf("Found 20: %d\n", search(&n1, 20));  /* 1 */
    printf("Found 99: %d\n", search(&n1, 99));  /* 0 */
    return 0;
}

10 -> 20 -> 30 -> NULL
10 -> 20 -> 30 -> NULL
Reverse: 30 20 10 
Count: 3
Found 20: 1
Found 99: 0

Key Points

•Iterative traversal: O(n) time, O(1) space
•Recursive traversal: O(n) time, O(n) space (call stack)
•Reverse printing via recursion: print after the recursive call
•Always check for NULL before accessing node members
•The head pointer is not modified during traversal (use a local copy)

Gotchas

•Modifying head directly (head = head->next) in a function that takes Node *head is safe since it is a local copy, but confusing -- prefer a separate curr variable
•Recursive traversal on a very long list causes stack overflow
•Infinite loop if the list has a cycle and you do not check for it
•Forgetting the NULL check at the start causes segfault on empty list

Start at head, follow next pointers until NULL. Use iterative (O(1) space) or recursive (O(n) space). For reverse print, use recursion and print after the recursive call.

•Iterative: O(n) time, O(1) space
•Use a curr pointer, do not modify head

void printList(Node *head) {
    Node *curr = head;
    while (curr) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

Infinite loop if the list has a cycle

Question 5 / 15

How do you reverse a singly linked list iteratively and recursively?

Reversing a linked list is one of the most common interview questions. There are two approaches:

Iterative (O(n) time, O(1) space): Use three pointers: prev, curr, next. At each step, save curr->next, point curr->next to prev, advance prev and curr.

Recursive (O(n) time, O(n) space): Recurse to the end of the list. On the way back, each node sets node->next->next = node (makes the next node point back) and node->next = NULL (breaks forward link).

The iterative approach is preferred in practice because it uses O(1) extra space.

Pseudo Code

IterativeReverse(head):
  prev = NULL
  curr = *head
  while curr != NULL:
    next = curr->next    // save next
    curr->next = prev    // reverse link
    prev = curr          // advance prev
    curr = next          // advance curr
  *head = prev           // new head

RecursiveReverse(node):
  if node is NULL or node->next is NULL:
    return node          // base case: last node becomes new head
  newHead = RecursiveReverse(node->next)
  node->next->next = node  // reverse the link
  node->next = NULL        // break forward link
  return newHead

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Iterative reverse: O(n) time, O(1) space */
void reverseIterative(Node **head) {
    Node *prev = NULL;
    Node *curr = *head;
    Node *next = NULL;

    while (curr != NULL) {
        next = curr->next;   /* save next */
        curr->next = prev;   /* reverse link */
        prev = curr;         /* advance prev */
        curr = next;         /* advance curr */
    }
    *head = prev;            /* prev is the new head */
}

/* Recursive reverse: O(n) time, O(n) space */
Node *reverseRecursive(Node *node) {
    /* Base case: empty list or single node */
    if (node == NULL || node->next == NULL)
        return node;

    Node *newHead = reverseRecursive(node->next);
    node->next->next = node;  /* make next node point back to us */
    node->next = NULL;        /* remove our forward link */
    return newHead;
}

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    /* Build list: 1 -> 2 -> 3 -> 4 -> 5 */
    Node *head = NULL;
    for (int i = 5; i >= 1; i--) {
        Node *n = createNode(i);
        n->next = head;
        head = n;
    }

    printf("Original: ");
    printList(head);  /* 1 -> 2 -> 3 -> 4 -> 5 -> NULL */

    reverseIterative(&head);
    printf("Reversed (iterative): ");
    printList(head);  /* 5 -> 4 -> 3 -> 2 -> 1 -> NULL */

    head = reverseRecursive(head);
    printf("Reversed again (recursive): ");
    printList(head);  /* 1 -> 2 -> 3 -> 4 -> 5 -> NULL */

    return 0;
}

Original: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Reversed (iterative): 5 -> 4 -> 3 -> 2 -> 1 -> NULL
Reversed again (recursive): 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Key Points

•Iterative uses three pointers (prev, curr, next): O(1) space
•Recursive uses the call stack: O(n) space
•After iterative reverse, prev becomes the new head
•Recursive: node->next->next = node reverses the link on the way back
•Both approaches are O(n) time

Gotchas

•Forgetting to set node->next = NULL in recursive version creates a cycle between the first two nodes
•Forgetting to update *head = prev in iterative version means head still points to the old first node (now the last)
•Recursive reverse on a very long list can cause stack overflow
•Must save curr->next before overwriting curr->next = prev

Iterative: Three pointers (prev, curr, next). At each step: save next, reverse link, advance. Recursive: Recurse to end, then node->next->next = node; node->next = NULL; on the way back.

•Iterative: O(1) space with prev/curr/next pointers
•Recursive: O(n) space, reverse links on the way back

void reverseIterative(Node **head) {
    Node *prev = NULL, *curr = *head, *next;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

Node *reverseRecursive(Node *node) {
    if (!node || !node->next) return node;
    Node *newHead = reverseRecursive(node->next);
    node->next->next = node;
    node->next = NULL;
    return newHead;
}

Forgetting node->next = NULL in recursive version creates a cycle

Question 6 / 15

How do you detect a cycle in a linked list using Floyd's algorithm?

Floyd's Cycle Detection (Tortoise and Hare) uses two pointers moving at different speeds:

Slow pointer: moves 1 step at a time
Fast pointer: moves 2 steps at a time

If there is a cycle, the fast pointer will eventually catch up to the slow pointer (they will meet inside the cycle). If there is no cycle, the fast pointer will reach NULL.

Why it works: In a cycle of length C, the fast pointer closes the gap by 1 node per iteration. So they must meet within C iterations after both enter the cycle.

Finding the cycle start: After detection, reset one pointer to head. Move both pointers one step at a time. They will meet at the start of the cycle. This works because of the mathematical relationship between the distances.

Time: O(n), Space: O(1).

Pseudo Code

DetectCycle(head):
  slow = head
  fast = head
  while fast != NULL and fast->next != NULL:
    slow = slow->next        // 1 step
    fast = fast->next->next   // 2 steps
    if slow == fast:
      return true  // cycle found
  return false  // no cycle

FindCycleStart(head):
  // First detect cycle
  slow = fast = head
  while fast and fast->next:
    slow = slow->next
    fast = fast->next->next
    if slow == fast: break
  if fast == NULL or fast->next == NULL:
    return NULL  // no cycle
  // Reset slow to head, move both 1 step
  slow = head
  while slow != fast:
    slow = slow->next
    fast = fast->next
  return slow  // start of cycle

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Detect if a cycle exists: returns 1 if cycle, 0 otherwise */
int hasCycle(Node *head) {
    Node *slow = head;
    Node *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;  /* cycle detected */
    }
    return 0;  /* no cycle */
}

/* Find the starting node of the cycle, or NULL if no cycle */
Node *findCycleStart(Node *head) {
    Node *slow = head;
    Node *fast = head;

    /* Phase 1: Detect cycle */
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            break;
    }

    /* No cycle */
    if (fast == NULL || fast->next == NULL)
        return NULL;

    /* Phase 2: Find start of cycle */
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;  /* both move 1 step now */
    }
    return slow;  /* start of cycle */
}

int main(void) {
    /* Create: 1 -> 2 -> 3 -> 4 -> 5 -> back to 3 */
    Node *n1 = createNode(1);
    Node *n2 = createNode(2);
    Node *n3 = createNode(3);
    Node *n4 = createNode(4);
    Node *n5 = createNode(5);
    n1->next = n2; n2->next = n3; n3->next = n4;
    n4->next = n5; n5->next = n3;  /* cycle! */

    printf("Has cycle: %d\n", hasCycle(n1));  /* 1 */

    Node *start = findCycleStart(n1);
    if (start)
        printf("Cycle starts at node with data: %d\n", start->data);  /* 3 */

    /* Break cycle for cleanup */
    n5->next = NULL;
    /* free nodes... */
    return 0;
}

Has cycle: 1
Cycle starts at node with data: 3

Key Points

•Floyd's algorithm: slow moves 1 step, fast moves 2 steps
•If they meet, a cycle exists; if fast reaches NULL, no cycle
•To find cycle start: reset slow to head, move both 1 step until they meet
•O(n) time, O(1) space -- no hash table needed
•Check both fast != NULL and fast->next != NULL to avoid segfault

Gotchas

•Must check both fast != NULL AND fast->next != NULL before advancing fast by 2
•Comparing pointer addresses (slow == fast), not data values
•The meeting point is NOT necessarily the start of the cycle
•Cannot free nodes in a cyclic list without first breaking the cycle

Floyd's Tortoise and Hare: slow pointer moves 1 step, fast moves 2. If they meet, cycle exists. To find cycle start: reset slow to head, move both 1 step until they meet again. O(n) time, O(1) space.

•Slow pointer (1 step) and fast pointer (2 steps)
•O(n) time, O(1) space

int hasCycle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

Must check both fast != NULL and fast->next != NULL before advancing

Question 7 / 15

How do you find the middle node of a linked list using the slow/fast pointer technique?

The slow/fast pointer (tortoise and hare) technique finds the middle in a single pass:

Slow moves 1 step per iteration
Fast moves 2 steps per iteration

When fast reaches the end, slow is at the middle.

Even-length lists: Depending on the loop condition, you get either the first or second middle node:

while (fast && fast->next) -- slow lands on the second middle (e.g., for 1->2->3->4, slow is at 3)
while (fast->next && fast->next->next) -- slow lands on the first middle (e.g., slow is at 2)

Time: O(n), Space: O(1). Only requires a single traversal.

Pseudo Code

FindMiddle(head):
  slow = head
  fast = head
  while fast != NULL and fast->next != NULL:
    slow = slow->next
    fast = fast->next->next
  return slow  // middle node

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Returns the middle node (second middle for even-length lists) */
Node *findMiddle(Node *head) {
    if (head == NULL) return NULL;

    Node *slow = head;
    Node *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

/* Returns first middle for even-length lists */
Node *findFirstMiddle(Node *head) {
    if (head == NULL) return NULL;

    Node *slow = head;
    Node *fast = head;

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

int main(void) {
    /* Odd: 1 -> 2 -> 3 -> 4 -> 5 */
    Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("Middle (odd): %d\n", findMiddle(head)->data);  /* 3 */

    /* Even: 1 -> 2 -> 3 -> 4 */
    Node *head2 = createNode(1);
    head2->next = createNode(2);
    head2->next->next = createNode(3);
    head2->next->next->next = createNode(4);

    printf("Middle (even, 2nd): %d\n", findMiddle(head2)->data);       /* 3 */
    printf("Middle (even, 1st): %d\n", findFirstMiddle(head2)->data);  /* 2 */

    return 0;
}

Middle (odd): 3
Middle (even, 2nd): 3
Middle (even, 1st): 2

Key Points

•Slow/fast pointer: slow at middle when fast reaches end
•Single pass: O(n) time, O(1) space
•Loop condition determines which middle for even-length lists
•while(fast && fast->next) gives second middle for even lists
•Useful as a building block for merge sort on linked lists

Gotchas

•For even-length lists, the 'middle' depends on your loop condition -- interviewers may ask for either
•Must handle NULL head to avoid segfault
•Do not confuse with cycle detection -- same technique but different purpose
•If the list has a cycle, this function loops forever

Slow pointer moves 1 step, fast moves 2. When fast hits end, slow is at the middle. O(n) time, O(1) space, single pass.

•Slow/fast pointer gives middle in one pass
•O(n) time, O(1) space

Node *findMiddle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  /* middle node */
}

For even-length lists, loop condition determines first or second middle

Question 8 / 15

How do you merge two sorted linked lists into one sorted list?

Merging two sorted linked lists is a classic problem (used in merge sort for linked lists). The idea is similar to the merge step in merge sort:

Create a dummy head node to simplify edge cases
Compare the heads of both lists
Attach the smaller node to the result and advance that list's pointer
When one list is exhausted, attach the remainder of the other list

Dummy node trick: Using a dummy/sentinel node at the start avoids special-casing the first element. The result starts at dummy.next.

Time: O(n + m), Space: O(1) -- we reuse existing nodes, no new allocation needed.

Pseudo Code

MergeSorted(l1, l2):
  dummy = Node(0)  // sentinel
  tail = dummy
  while l1 != NULL and l2 != NULL:
    if l1->data <= l2->data:
      tail->next = l1
      l1 = l1->next
    else:
      tail->next = l2
      l2 = l2->next
    tail = tail->next
  tail->next = (l1 != NULL) ? l1 : l2
  return dummy.next

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Merge two sorted lists into one sorted list (iterative) */
Node *mergeSorted(Node *l1, Node *l2) {
    Node dummy;          /* stack-allocated sentinel */
    dummy.next = NULL;
    Node *tail = &dummy;

    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    /* Attach remaining nodes */
    tail->next = (l1 != NULL) ? l1 : l2;

    return dummy.next;
}

/* Recursive merge */
Node *mergeSortedRecursive(Node *l1, Node *l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    if (l1->data <= l2->data) {
        l1->next = mergeSortedRecursive(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSortedRecursive(l1, l2->next);
        return l2;
    }
}

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    /* List 1: 1 -> 3 -> 5 */
    Node *l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);

    /* List 2: 2 -> 4 -> 6 */
    Node *l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);

    Node *merged = mergeSorted(l1, l2);
    printList(merged);  /* 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL */

    return 0;
}

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Key Points

•Use a dummy/sentinel node to avoid special-casing the first element
•Compare heads of both lists and attach the smaller one
•When one list is exhausted, attach the rest of the other
•O(n + m) time, O(1) space (iterative) -- reuses existing nodes
•Recursive version is elegant but uses O(n + m) stack space

Gotchas

•The dummy node should be stack-allocated (not malloc'd) to avoid memory leaks
•This modifies the original lists' next pointers -- the originals are consumed
•Using <= (not <) preserves stability (equal elements keep original order)
•Forgetting to attach the remaining list loses those elements

Use a dummy sentinel node. Compare heads of both lists, attach the smaller one, advance. When one list is done, attach the rest of the other. O(n+m) time, O(1) space.

•Dummy node simplifies edge cases
•O(n + m) time, O(1) space

Node *mergeSorted(Node *l1, Node *l2) {
    Node dummy;
    Node *tail = &dummy;
    while (l1 && l2) {
        if (l1->data <= l2->data) {
            tail->next = l1; l1 = l1->next;
        } else {
            tail->next = l2; l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

Original lists are consumed (next pointers modified)

Question 9 / 15

How do you implement a doubly linked list in C?

A doubly linked list has nodes with both next and prev pointers, allowing traversal in both directions.

Advantages over singly linked:

Delete a node given only a pointer to it: O(1) (no need to find prev)
Traverse backwards
Insert before a given node: O(1)

Disadvantages:

Extra memory per node (one more pointer)
More pointers to maintain on insert/delete (more error-prone)

Insert/delete must update both next and prev pointers of affected nodes. The order of pointer updates is critical to avoid losing references.

Pseudo Code

Node structure:
  int data
  Node *prev
  Node *next

InsertAtHead(head, value):
  new = createNode(value)
  new->next = *head
  if *head != NULL:
    (*head)->prev = new
  *head = new

DeleteNode(head, node):
  if node->prev != NULL:
    node->prev->next = node->next
  else:
    *head = node->next  // deleting head
  if node->next != NULL:
    node->next->prev = node->prev
  free(node)

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode *createDNode(int val) {
    DNode *n = (DNode *)malloc(sizeof(DNode));
    if (!n) { perror("malloc"); exit(1); }
    n->data = val;
    n->prev = NULL;
    n->next = NULL;
    return n;
}

/* Insert at head */
void insertAtHead(DNode **head, int val) {
    DNode *newNode = createDNode(val);
    newNode->next = *head;
    if (*head != NULL)
        (*head)->prev = newNode;
    *head = newNode;
}

/* Insert at tail */
void insertAtTail(DNode **head, int val) {
    DNode *newNode = createDNode(val);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    DNode *curr = *head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = newNode;
    newNode->prev = curr;
}

/* Delete a given node (O(1) if you have the pointer) */
void deleteNode(DNode **head, DNode *node) {
    if (node == NULL) return;

    if (node->prev != NULL)
        node->prev->next = node->next;
    else
        *head = node->next;  /* deleting head */

    if (node->next != NULL)
        node->next->prev = node->prev;

    free(node);
}

void printForward(DNode *head) {
    printf("Forward: ");
    DNode *curr = head;
    DNode *last = NULL;
    while (curr) {
        printf("%d <-> ", curr->data);
        last = curr;
        curr = curr->next;
    }
    printf("NULL\n");
}

void printBackward(DNode *tail) {
    printf("Backward: ");
    while (tail) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("NULL\n");
}

int main(void) {
    DNode *head = NULL;
    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);
    insertAtHead(&head, 5);

    printForward(head);  /* Forward: 5 <-> 10 <-> 20 <-> 30 <-> NULL */

    /* Delete the second node (10) */
    deleteNode(&head, head->next);
    printForward(head);  /* Forward: 5 <-> 20 <-> 30 <-> NULL */

    return 0;
}

Forward: 5 <-> 10 <-> 20 <-> 30 <-> NULL
Forward: 5 <-> 20 <-> 30 <-> NULL

Key Points

•Each node has both prev and next pointers
•Deletion with a known node pointer is O(1) -- no need to find predecessor
•Can traverse in both directions
•Extra pointer per node uses more memory than singly linked list
•Must update both prev and next pointers on insert/delete

Gotchas

•Forgetting to update prev pointer of the node after the new node on insertion
•Deleting head requires updating the head pointer AND setting new head's prev to NULL
•More pointer updates means more chances for bugs and dangling pointers
•Must check for NULL before accessing prev or next (head->prev and tail->next are NULL)

Each node has prev and next pointers. Allows O(1) deletion given a node pointer and bidirectional traversal. More memory per node, more pointer updates on insert/delete.

•O(1) deletion given a node pointer
•Bidirectional traversal

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

void deleteNode(DNode **head, DNode *node) {
    if (node->prev) node->prev->next = node->next;
    else *head = node->next;
    if (node->next) node->next->prev = node->prev;
    free(node);
}

Must update both prev and next pointers on every insert/delete

Question 10 / 15

How do you implement a circular linked list in C?

In a circular linked list, the last node's next pointer points back to the head instead of NULL. This creates a ring structure.

Use cases:

Round-robin scheduling
Circular buffers
Josephus problem
Multiplayer game turn order

Key differences from linear lists:

No NULL at the end -- traversal must check if you've returned to the starting node
Insertion/deletion must maintain the circular link
Can start traversal from any node and visit all nodes

Variant: In a circular doubly linked list, head->prev points to the tail and tail->next points to the head.

Pseudo Code

InsertAtHead(head, value):
  new = createNode(value)
  if *head == NULL:
    new->next = new  // points to itself
    *head = new
    return
  // Find the last node
  last = *head
  while last->next != *head:
    last = last->next
  new->next = *head
  last->next = new
  *head = new

Traverse(head):
  if head == NULL: return
  curr = head
  do:
    print(curr->data)
    curr = curr->next
  while curr != head

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Insert at the end of circular list */
void insertEnd(Node **head, int val) {
    Node *newNode = createNode(val);
    if (*head == NULL) {
        newNode->next = newNode;  /* points to itself */
        *head = newNode;
        return;
    }
    /* Find the last node */
    Node *last = *head;
    while (last->next != *head)
        last = last->next;
    last->next = newNode;
    newNode->next = *head;
}

/* Delete a node by value */
void deleteNode(Node **head, int val) {
    if (*head == NULL) return;

    Node *curr = *head;
    Node *prev = NULL;

    /* Single node case */
    if (curr->data == val && curr->next == *head) {
        free(curr);
        *head = NULL;
        return;
    }

    /* Deleting head */
    if (curr->data == val) {
        Node *last = *head;
        while (last->next != *head)
            last = last->next;
        *head = curr->next;
        last->next = *head;
        free(curr);
        return;
    }

    /* Find node to delete */
    prev = curr;
    curr = curr->next;
    while (curr != *head && curr->data != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == *head) return;  /* not found */

    prev->next = curr->next;
    free(curr);
}

/* Traverse using do-while */
void printCircular(Node *head) {
    if (head == NULL) {
        printf("(empty)\n");
        return;
    }
    Node *curr = head;
    do {
        printf("%d -> ", curr->data);
        curr = curr->next;
    } while (curr != head);
    printf("(back to %d)\n", head->data);
}

int main(void) {
    Node *head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    insertEnd(&head, 40);

    printCircular(head);  /* 10 -> 20 -> 30 -> 40 -> (back to 10) */

    deleteNode(&head, 20);
    printCircular(head);  /* 10 -> 30 -> 40 -> (back to 10) */

    return 0;
}

10 -> 20 -> 30 -> 40 -> (back to 10)
10 -> 30 -> 40 -> (back to 10)

Key Points

•Last node's next points to head (no NULL terminator)
•Single node: next points to itself
•Must use do-while for traversal (check after first iteration)
•Useful for round-robin scheduling and circular buffers
•Deletion of head requires finding and updating the last node

Gotchas

•Using while(curr->next != NULL) causes infinite loop -- there is no NULL
•Traversal must use do-while or track the starting node to know when to stop
•Single-node deletion (the only node) must set head to NULL
•Deleting head in circular list is more complex: must update last->next

Last node's next points back to head. Use do-while for traversal. Single node points to itself. No NULL terminator -- you stop when you return to the start.

•No NULL at end -- last->next == head
•Use do-while for traversal

void insertEnd(Node **head, int val) {
    Node *n = createNode(val);
    if (!*head) { n->next = n; *head = n; return; }
    Node *last = *head;
    while (last->next != *head) last = last->next;
    last->next = n;
    n->next = *head;
}

void printCircular(Node *head) {
    if (!head) return;
    Node *c = head;
    do {
        printf("%d -> ", c->data);
        c = c->next;
    } while (c != head);
    printf("(back to head)\n");
}

while(curr != NULL) causes infinite loop in a circular list

Question 11 / 15

How do you find the nth node from the end of a linked list?

Finding the nth node from the end is a classic two-pointer problem.

Two-pointer approach (single pass, O(n) time, O(1) space):

Move the first pointer n steps ahead
Then move both first and second one step at a time
When first reaches NULL, second is at the nth node from the end

Why it works: The two pointers maintain a gap of exactly n nodes. When the leading pointer hits the end, the trailing pointer is n positions from the end.

Alternative: Traverse once to get the length L, then traverse again to position L - n. This requires two passes.

Edge cases: n larger than list length, n = 0, single-node list.

Pseudo Code

NthFromEnd(head, n):
  first = head
  second = head
  // Move first n steps ahead
  for i = 0 to n-1:
    if first is NULL: return NULL  // n > length
    first = first->next
  // Move both until first reaches end
  while first != NULL:
    first = first->next
    second = second->next
  return second

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Find nth node from end (1-indexed: n=1 means last node) */
Node *nthFromEnd(Node *head, int n) {
    Node *first = head;
    Node *second = head;

    /* Move first n steps ahead */
    for (int i = 0; i < n; i++) {
        if (first == NULL) return NULL;  /* n > list length */
        first = first->next;
    }

    /* Move both until first reaches NULL */
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }

    return second;
}

int main(void) {
    /* Build: 10 -> 20 -> 30 -> 40 -> 50 */
    Node *head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);
    head->next->next->next->next = createNode(50);

    Node *result = nthFromEnd(head, 2);  /* 2nd from end */
    if (result)
        printf("2nd from end: %d\n", result->data);  /* 40 */

    result = nthFromEnd(head, 5);  /* 5th from end = head */
    if (result)
        printf("5th from end: %d\n", result->data);  /* 10 */

    result = nthFromEnd(head, 6);  /* beyond list */
    printf("6th from end: %s\n", result ? "found" : "NULL");  /* NULL */

    return 0;
}

2nd from end: 40
5th from end: 10
6th from end: NULL

Key Points

•Two-pointer technique: maintain n-node gap between pointers
•Single pass: O(n) time, O(1) space
•1-indexed: n=1 returns the last node
•First move leading pointer n steps, then move both until leader hits NULL
•Alternative: two-pass method -- get length, then traverse to (length - n)

Gotchas

•Off-by-one: clarify if n is 0-indexed or 1-indexed with the interviewer
•n larger than list length -- must check for NULL during the initial advance
•n = 0 may be invalid depending on convention -- validate input
•Single-node list with n=1 should return that node

Two pointers with n-node gap. Move first pointer n steps ahead, then move both until first reaches NULL. Second pointer is at nth from end. O(n) time, O(1) space, single pass.

•Two pointers with n-node gap
•O(n) time, O(1) space

Node *nthFromEnd(Node *head, int n) {
    Node *first = head, *second = head;
    for (int i = 0; i < n; i++) {
        if (!first) return NULL;
        first = first->next;
    }
    while (first) {
        first = first->next;
        second = second->next;
    }
    return second;
}

Off-by-one: clarify 0-indexed vs 1-indexed with interviewer

Question 12 / 15

How do you remove duplicates from a sorted linked list?

Since the list is sorted, all duplicates are adjacent. Compare each node with its next node:

If equal, skip the next node (relink and free)
If not equal, advance to next

Time: O(n), Space: O(1)

For an unsorted list, you would need either:

Hash set: O(n) time, O(n) space
Nested loops: O(n^2) time, O(1) space

The sorted variant is the most commonly asked in interviews.

Pseudo Code

RemoveDuplicates(head):
  curr = head
  while curr != NULL and curr->next != NULL:
    if curr->data == curr->next->data:
      temp = curr->next
      curr->next = temp->next
      free(temp)
    else:
      curr = curr->next

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* Remove duplicates from sorted list */
void removeDuplicates(Node *head) {
    Node *curr = head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->data == curr->next->data) {
            Node *temp = curr->next;
            curr->next = temp->next;
            free(temp);
        } else {
            curr = curr->next;
        }
    }
}

/* Remove ALL nodes that have duplicates (keep only distinct values) */
void removeAllDuplicates(Node **head) {
    Node dummy;
    dummy.next = *head;
    Node *prev = &dummy;

    while (prev->next != NULL) {
        Node *curr = prev->next;
        /* Check if curr has duplicates ahead */
        while (curr->next != NULL && curr->data == curr->next->data) {
            Node *temp = curr->next;
            curr->next = temp->next;
            free(temp);
        }
        if (prev->next == curr) {
            prev = curr;  /* no duplicates, advance */
        } else {
            prev->next = curr->next;  /* remove curr too */
            free(curr);
        }
    }
    *head = dummy.next;
}

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    /* Sorted list with duplicates: 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 */
    Node *head = createNode(1);
    head->next = createNode(1);
    head->next->next = createNode(2);
    head->next->next->next = createNode(3);
    head->next->next->next->next = createNode(3);
    head->next->next->next->next->next = createNode(3);
    head->next->next->next->next->next->next = createNode(4);

    printf("Before: ");
    printList(head);  /* 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> NULL */

    removeDuplicates(head);
    printf("After:  ");
    printList(head);  /* 1 -> 2 -> 3 -> 4 -> NULL */

    return 0;
}

Before: 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> NULL
After:  1 -> 2 -> 3 -> 4 -> NULL

Key Points

•Sorted list: duplicates are adjacent, compare curr with curr->next
•Do NOT advance curr when deleting -- the new next might also be a duplicate
•O(n) time, O(1) space
•Variant: remove ALL occurrences of duplicated values (keep only unique)
•free() each removed node to prevent memory leaks

Gotchas

•Advancing curr when deleting misses consecutive duplicates (e.g., 1->1->1)
•Forgetting to free removed nodes causes memory leaks
•For unsorted lists, this approach does not work -- need hash set or O(n^2)
•Empty list and single-node list should be handled (the while condition handles both)

Sorted list: compare each node with its next. If equal, skip and free the duplicate. Do not advance on deletion (next might also be a duplicate). O(n) time, O(1) space.

•Compare adjacent nodes in sorted list
•Don't advance when deleting -- next might also be duplicate

void removeDuplicates(Node *head) {
    Node *curr = head;
    while (curr && curr->next) {
        if (curr->data == curr->next->data) {
            Node *tmp = curr->next;
            curr->next = tmp->next;
            free(tmp);
        } else {
            curr = curr->next;
        }
    }
}

Only works for sorted lists; unsorted needs hash set or O(n^2)

Question 13 / 15

How do you find the intersection point of two linked lists?

Two linked lists intersect when they share a common suffix -- from some node onward, they are the same list (same physical nodes, not just same values).

Approach 1 -- Length difference (most common):

Find lengths of both lists: L1 and L2
Advance the longer list's pointer by |L1 - L2| steps
Move both pointers one step at a time until they meet

Approach 2 -- Two-pointer trick (elegant):

Start pointer A at head of list 1, pointer B at head of list 2
When A reaches the end, redirect to head of list 2
When B reaches the end, redirect to head of list 1
They will meet at the intersection (or both become NULL)

Why Approach 2 works: Both pointers traverse L1 + L2 nodes total, so they are synchronized when they enter the common suffix.

Time: O(n + m), Space: O(1).

Pseudo Code

Approach 1 (Length difference):
  lenA = length(headA)
  lenB = length(headB)
  Advance longer list by |lenA - lenB| steps
  Move both forward until they meet or both are NULL

Approach 2 (Redirect trick):
  a = headA, b = headB
  while a != b:
    a = (a != NULL) ? a->next : headB
    b = (b != NULL) ? b->next : headA
  return a  // intersection or NULL

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

int getLength(Node *head) {
    int len = 0;
    while (head) { len++; head = head->next; }
    return len;
}

/* Approach 1: Length difference */
Node *getIntersection(Node *headA, Node *headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);

    /* Advance the longer list */
    while (lenA > lenB) { headA = headA->next; lenA--; }
    while (lenB > lenA) { headB = headB->next; lenB--; }

    /* Move both until they meet */
    while (headA != headB) {
        headA = headA->next;
        headB = headB->next;
    }
    return headA;  /* NULL if no intersection */
}

/* Approach 2: Two-pointer redirect trick */
Node *getIntersectionV2(Node *headA, Node *headB) {
    Node *a = headA;
    Node *b = headB;

    while (a != b) {
        a = (a != NULL) ? a->next : headB;
        b = (b != NULL) ? b->next : headA;
    }
    return a;  /* intersection node or NULL */
}

int main(void) {
    /* Common suffix: 7 -> 8 -> NULL */
    Node *common = createNode(7);
    common->next = createNode(8);

    /* List A: 1 -> 2 -> 7 -> 8 */
    Node *headA = createNode(1);
    headA->next = createNode(2);
    headA->next->next = common;

    /* List B: 3 -> 4 -> 5 -> 7 -> 8 */
    Node *headB = createNode(3);
    headB->next = createNode(4);
    headB->next->next = createNode(5);
    headB->next->next->next = common;

    Node *inter = getIntersection(headA, headB);
    if (inter)
        printf("Intersection at: %d\n", inter->data);  /* 7 */

    inter = getIntersectionV2(headA, headB);
    if (inter)
        printf("Intersection (v2) at: %d\n", inter->data);  /* 7 */

    return 0;
}

Intersection at: 7
Intersection (v2) at: 7

Key Points

•Intersection means same physical node (pointer equality), not same value
•Length difference method: align starting positions, then walk together
•Redirect trick: both traverse L1 + L2 total, synchronizing at intersection
•O(n + m) time, O(1) space for both approaches
•If no intersection, both methods return NULL

Gotchas

•Comparing data values instead of pointer addresses is a common mistake
•The two lists form a Y shape after intersection -- they cannot diverge again
•Approach 2 loops forever if one list has a cycle -- only works on acyclic lists
•In the redirect trick, must use a != NULL (not a->next) to handle the redirect at NULL

Two-pointer redirect: pointer A starts at list 1, pointer B at list 2. When one reaches NULL, redirect to the other list's head. They meet at the intersection (or both become NULL). O(n+m) time, O(1) space.

•Both pointers traverse L1 + L2 nodes, meeting at intersection
•O(n + m) time, O(1) space

Node *getIntersection(Node *headA, Node *headB) {
    Node *a = headA, *b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;  /* intersection or NULL */
}

Compare pointer addresses, not data values

Question 14 / 15

How do you clone a linked list that has both next and random pointers?

Each node has a next pointer and a random pointer that can point to any node in the list or NULL. The goal is to create a deep copy where all pointers in the clone refer to the cloned nodes, not the originals.

Approach 1 -- Hash map (O(n) time, O(n) space):

Create a copy of each node and store original->copy mapping
Second pass: set each copy's next and random using the map

Approach 2 -- Interleaving (O(n) time, O(1) space):

Insert cloned nodes between originals: A -> A' -> B -> B' -> C -> C'
Set random pointers: clone->random = original->random->next
Separate the two lists

The interleaving approach is the most elegant interview answer.

Pseudo Code

Interleaving approach:
Step 1: Insert copies
  curr = head
  while curr:
    copy = new Node(curr->data)
    copy->next = curr->next
    curr->next = copy
    curr = copy->next

Step 2: Set random pointers
  curr = head
  while curr:
    clone = curr->next
    clone->random = curr->random ? curr->random->next : NULL
    curr = clone->next

Step 3: Separate lists
  curr = head
  cloneHead = head->next
  while curr:
    clone = curr->next
    curr->next = clone->next
    clone->next = clone->next ? clone->next->next : NULL
    curr = curr->next

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct RNode {
    int data;
    struct RNode *next;
    struct RNode *random;
} RNode;

RNode *createRNode(int val) {
    RNode *n = (RNode *)malloc(sizeof(RNode));
    n->data = val;
    n->next = NULL;
    n->random = NULL;
    return n;
}

/* Clone using interleaving: O(n) time, O(1) extra space */
RNode *cloneList(RNode *head) {
    if (head == NULL) return NULL;

    /* Step 1: Insert copy after each original node */
    RNode *curr = head;
    while (curr != NULL) {
        RNode *copy = createRNode(curr->data);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }

    /* Step 2: Set random pointers for copies */
    curr = head;
    while (curr != NULL) {
        RNode *copy = curr->next;
        copy->random = (curr->random != NULL) ? curr->random->next : NULL;
        curr = copy->next;
    }

    /* Step 3: Separate the two interleaved lists */
    RNode *cloneHead = head->next;
    curr = head;
    while (curr != NULL) {
        RNode *copy = curr->next;
        curr->next = copy->next;
        copy->next = (copy->next != NULL) ? copy->next->next : NULL;
        curr = curr->next;
    }

    return cloneHead;
}

void printRList(RNode *head) {
    while (head) {
        printf("[%d, random->%s] -> ", head->data,
               head->random ? (char[12]){0} : "NULL");
        if (head->random) printf("(%d) ", head->random->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    RNode *n1 = createRNode(1);
    RNode *n2 = createRNode(2);
    RNode *n3 = createRNode(3);
    n1->next = n2; n2->next = n3;
    n1->random = n3;  /* 1's random -> 3 */
    n2->random = n1;  /* 2's random -> 1 */
    n3->random = n2;  /* 3's random -> 2 */

    RNode *clone = cloneList(n1);

    /* Verify clone is independent */
    printf("Original: %d, Clone: %d\n", n1->data, clone->data);
    printf("Same memory? %s\n", (n1 == clone) ? "YES" : "NO");  /* NO */
    printf("Clone random: %d\n", clone->random->data);  /* 3 */
    printf("Clone->next->random: %d\n", clone->next->random->data);  /* 1 */

    return 0;
}

Original: 1, Clone: 1
Same memory? NO
Clone random: 3
Clone->next->random: 1

Key Points

•Three-step interleaving: insert copies, set randoms, separate lists
•Interleaving achieves O(1) extra space without a hash map
•clone->random = original->random->next works because copies are interleaved
•Must restore the original list during the separation step
•Hash map approach is simpler but uses O(n) extra space

Gotchas

•Forgetting to restore the original list in step 3 corrupts both lists
•NULL checks are critical: random can be NULL, and at list end next can be NULL
•In C there is no built-in hash map -- you would need to implement one or use interleaving
•This is a deep copy -- modifying the clone must not affect the original

Interleaving method: (1) insert copy after each node, (2) set random pointers using copy->random = original->random->next, (3) separate the lists. O(n) time, O(1) extra space.

•Three steps: interleave, set randoms, separate
•O(n) time, O(1) extra space

typedef struct RNode {
    int data;
    struct RNode *next;
    struct RNode *random;
} RNode;

RNode *cloneList(RNode *head) {
    if (!head) return NULL;
    /* Step 1: Interleave copies */
    for (RNode *c = head; c; c = c->next->next) {
        RNode *cp = createRNode(c->data);
        cp->next = c->next; c->next = cp;
    }
    /* Step 2: Set random pointers */
    for (RNode *c = head; c; c = c->next->next)
        c->next->random = c->random ? c->random->next : NULL;
    /* Step 3: Separate */
    RNode *clone = head->next;
    for (RNode *c = head; c; c = c->next) {
        RNode *cp = c->next;
        c->next = cp->next;
        cp->next = cp->next ? cp->next->next : NULL;
    }
    return clone;
}

Must restore original list in step 3 or both lists are corrupted

Question 15 / 15

How do you properly free all nodes in a linked list to avoid memory leaks?

Freeing a linked list requires careful traversal because once you free() a node, you cannot access its next pointer. You must save next before freeing.

Correct pattern:

Save curr->next in a temporary pointer
Free curr
Advance to the saved next pointer

Common mistakes:

free(head) then accessing head->next -- undefined behavior (use-after-free)
Freeing only the head -- leaks all remaining nodes
Not setting the head pointer to NULL after freeing -- dangling pointer

For doubly linked lists: Same principle -- save next before freeing.

For circular lists: Must detect when you've gone around the full circle.

Pseudo Code

FreeList(head):
  curr = *head
  while curr != NULL:
    next = curr->next   // save before free
    free(curr)
    curr = next
  *head = NULL           // prevent dangling pointer

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* CORRECT: Free all nodes safely */
void freeList(Node **head) {
    Node *curr = *head;
    while (curr != NULL) {
        Node *next = curr->next;  /* save next BEFORE freeing */
        free(curr);
        curr = next;
    }
    *head = NULL;  /* prevent dangling pointer */
}

/* WRONG: use-after-free bug */
void freeListBUGGY(Node *head) {
    while (head != NULL) {
        free(head);          /* freed! */
        head = head->next;   /* BUG: accessing freed memory */
    }
}

/* Free circular linked list */
void freeCircularList(Node **head) {
    if (*head == NULL) return;

    Node *curr = (*head)->next;
    while (curr != *head) {
        Node *next = curr->next;
        free(curr);
        curr = next;
    }
    free(*head);  /* free the head last */
    *head = NULL;
}

int main(void) {
    /* Build list */
    Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    printf("Before free: head = %p\n", (void *)head);

    freeList(&head);

    printf("After free: head = %p\n", (void *)head);  /* (nil) / 0x0 */

    return 0;
}

Before free: head = 0x...
After free: head = 0x0
(Note: first address is a heap pointer; exact value varies per run)

Key Points

•Save next pointer BEFORE calling free() on the current node
•Set head to NULL after freeing to avoid dangling pointer
•Pass Node **head so the caller's pointer gets NULLed
•For circular lists, stop when you return to the starting node
•Use valgrind to verify all nodes are freed (no leaks)

Gotchas

•Accessing node->next after free(node) is undefined behavior (use-after-free)
•Freeing only the head node leaks the rest of the list
•Not NULLing the head pointer after freeing leaves a dangling pointer
•Double-free: calling freeList twice on the same list without NULLing head crashes
•In circular lists, naive traversal with while(curr != NULL) never terminates

Save curr->next before calling free(curr), then advance. Set head to NULL after freeing all nodes to prevent dangling pointer.

•Save next before free, NULL out head after
•Pass Node **head to NULL the caller's pointer

void freeList(Node **head) {
    Node *curr = *head;
    while (curr) {
        Node *next = curr->next;
        free(curr);
        curr = next;
    }
    *head = NULL;
}

Accessing node->next after free(node) is undefined behavior

Built by onllm.dev

Home GitHub Support awesomePrep