Linked Lists and Pointer Manipulation Questions

Comprehensive knowledge of linked list data structures and pointer based implementations. Covers singly linked lists, doubly linked lists, circular lists, and node based sequential structures. Candidates should be able to implement and reason about core operations including traversal, insertion, deletion, reversing a list, finding the middle element, removing the nth node from the end, detecting and removing cycles, merging sorted lists, partitioning lists, computing intersection nodes, and other in place transformations. Emphasize pointer and reference manipulation techniques, manual memory allocation and deallocation, ownership and lifetime considerations, and debugging strategies for pointer errors and memory leaks, particularly in manual memory management languages such as C and C plus plus. Also cover implementation techniques such as iterative and recursive approaches, use of dummy head or sentinel nodes to simplify edge cases, and in place algorithms to minimize extra memory. Discuss algorithmic complexity and trade offs relative to contiguous arrays, including dynamic resizing, memory locality, and cache behavior, and when linked lists are the appropriate abstraction such as in embedded systems or when implementing free lists and adjacency lists. Interviewers may probe both low level pointer manipulation and higher level reasoning about when to use list based structures and how list concepts extend into more complex data structures.

EasyTechnical

59 practiced

Write a method in Java that merges two sorted singly linked lists of integers into a single sorted linked list and returns its head. Use an iterative approach and a dummy head sentinel. Provide time and space complexity and discuss trade-offs with the recursive alternative.

Sample Answer

**Approach (brief)**Use an iterative merge with a dummy head sentinel to simplify edge cases. Walk both lists, attach the smaller node each step, and return dummy.next.

**Code**

java

// Definition for singly-linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // sentinel
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            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;
}

**Complexity**- Time: O(n + m) where n,m are lengths of input lists.- Space: O(1) extra (reuses nodes). Recursive version has O(n + m) call-stack space.

**Trade-offs**- Iterative avoids call-stack overflow for long lists (production-safe).- Recursive can be more concise/readable but risks stack overflow and higher memory usage. Iterative is preferred in backend services for robustness.

HardTechnical

41 practiced

For backend services processing large linked data structures, explain strategies to minimize memory overhead and improve cache locality for linked lists: block allocation, pooling, array-of-structs, struct-of-arrays, pointer compression, packed nodes, and trade-offs between pointer-based lists and contiguous arrays or CSR representations.

MediumTechnical

32 practiced

Implement in Java a function that partitions a singly linked list around value x such that nodes less than x come before nodes greater or equal to x, preserving original relative order within each partition. Use O(1) extra space and a single pass. Provide time and space complexity.

Sample Answer

**Approach (brief)** Create two sublists: "less" and "greaterOrEqual". Iterate once, appending nodes to appropriate tail while reusing nodes (O(1) extra space). Preserve relative order by always appending to tail. Finally link less tail to greater head and terminate list.

**Code (Java)**

java

class ListNode {
    int val;
    ListNode next;
    ListNode(int v){ val = v; }
}

public ListNode partition(ListNode head, int x) {
    if (head == null) return null;
    ListNode lessHead = null, lessTail = null;
    ListNode geHead = null, geTail = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next; // detach safely
        cur.next = null;
        if (cur.val < x) {
            if (lessHead == null) lessHead = lessTail = cur;
            else { lessTail.next = cur; lessTail = cur; }
        } else {
            if (geHead == null) geHead = geTail = cur;
            else { geTail.next = cur; geTail = cur; }
        }
        cur = next;
    }
    if (lessTail != null) {
        lessTail.next = geHead;
        return lessHead;
    } else {
        return geHead;
    }
}

**Explanation & Complexity**- Single pass, stable because nodes appended to tails in original order.- Time: O(n). Space: O(1) extra (only constant pointers).- Edge cases: all nodes < x, all >= x, empty list, duplicates.

HardTechnical

37 practiced

Implement an iterative bottom-up merge sort for a singly linked list in C to avoid recursive stack depth. Describe the algorithm that merges sublists of size 1,2,4,... and implement pointer bookkeeping necessary to split and merge sublists in O(n log n) time and O(1) extra space.

Sample Answer

**Approach (brief)**Use iterative bottom-up merge sort: repeatedly merge adjacent sublists of size sz = 1,2,4,... until sz >= n. Operate in-place on singly linked list using O(1) extra space by splitting via pointer traversal and relinking merged lists. Maintain a dummy head and tail pointer to append merged runs.

// Iterative bottom-up merge sort for singly linked list
#include <stdlib.h>

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

// Split off first 'size' nodes from head, return head of remainder.
// Also terminate the returned run (its last->next = NULL).
static Node* split(Node* head, int size) {
    Node* cur = head;
    for (int i = 1; cur && i < size; ++i) cur = cur->next;
    if (!cur) return NULL;
    Node* rest = cur->next;
    cur->next = NULL;
    return rest;
}

// Merge two sorted lists a and b, attach to tail; return new tail.
static Node* merge_and_attach(Node* a, Node* b, Node* tail) {
    Node* cur = tail;
    while (a && b) {
        if (a->val <= b->val) { cur->next = a; a = a->next; }
        else { cur->next = b; b = b->next; }
        cur = cur->next;
    }
    cur->next = a ? a : b;
    while (cur->next) cur = cur->next;
    return cur;
}

Node* sortList(Node* head) {
    if (!head || !head->next) return head;
    // compute length
    int n = 0; for (Node* p = head; p; p = p->next) ++n;
    Node dummy; dummy.next = head;
    for (int sz = 1; sz < n; sz <<= 1) {
        Node* prev = &dummy;
        Node* cur = dummy.next;
        while (cur) {
            Node* left = cur;
            Node* right = split(left, sz);
            cur = split(right, sz); // remainder after right run
            prev = merge_and_attach(left, right, prev);
        }
    }
    return dummy.next;
}

Key points and complexity- Pointer bookkeeping: split returns remainder and severs runs; merge_and_attach appends merged run to tail and returns new tail.- Time: O(n log n). Space: O(1) extra (iterative, no recursion).- Edge cases: empty list, single node, duplicate values, odd-sized tail runs (split handles NULL runs).

EasyTechnical

40 practiced

Implement a stack using a singly linked list in Python with push, pop, peek, and is_empty methods. Discuss time complexity of each operation, memory usage per element, and when a linked list backed stack is preferable to a list-backed stack in backend code.

Sample Answer

**Approach**Use a singly linked list where head is the stack top. push/pop are O(1) by inserting/removing at head.

python

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedStack:
    def __init__(self):
        self.head = None  # top of stack
        self.size = 0

    def push(self, value):
        # create new node and link at head => O(1)
        self.head = Node(value, self.head)
        self.size += 1

    def pop(self):
        # remove head => O(1)
        if self.head is None:
            raise IndexError("pop from empty stack")
        val = self.head.value
        self.head = self.head.next
        self.size -= 1
        return val

    def peek(self):
        if self.head is None:
            raise IndexError("peek from empty stack")
        return self.head.value

    def is_empty(self):
        return self.head is None

    def __len__(self):
        return self.size

**Key concepts & complexity**- push: O(1) time, O(1) extra memory for node- pop: O(1) time- peek/is_empty/len: O(1)- Memory per element: one Node object (value reference + next pointer + object overhead). In CPython this is heavier than list element references.

**When to prefer linked-list stack (backend)**- When you need deterministic O(1) push/pop without occasional list resizing/copying spikes (real-time constraints).- When frequent inserts/removals at one end with unpredictable large size and you want predictable memory allocation patterns.- Otherwise Python list-backed stack (append/pop) is simpler, memory- and cache-friendlier, and usually faster for typical backend workloads.

Unlock Full Question Bank

Get access to hundreds of Linked Lists and Pointer Manipulation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.