Interview conceptCoding & Algorithms

In-Place Arrays And Linked List Manipulation

Asked of: Software Engineer

Last updated

Editorial trace showing backward two-pointer array merging and linked-list splicing, with i, j, write, n, y, and saved boundary pointers.

What's being tested

These problems test in-place manipulation: preserving useful structure while modifying arrays or linked lists with O(1) auxiliary space. You must demonstrate two-pointer traversal, careful boundary handling, and accurate time-complexity analysis without allocating a replacement collection.

Patterns & templates

  • Backward two-pointer merge — when the destination array has trailing capacity, compare from the ends; runs in O(m+n) time and O(1) space.

  • Maintain i, j, and write; place the larger value at write--, preventing unread destination values from being overwritten.

  • Handle exhausted inputs explicitly: once one sorted prefix remains, copy it; the other suffix is already correctly positioned.

  • For linked-list splicing, locate predecessor node n, successor node y, and the second list’s tail before changing links.

  • Save boundary references before rewiring: afterY = y.next, then connect n.next to list two and its tail to afterY.

  • Clarify whether positions are zero- or one-based, whether n and y are inclusive, and whether either list may be empty.

  • State complexity precisely: traversal is O(N+M) time; pointer rewiring uses O(1) extra space, excluding input nodes.

Common pitfalls

Pitfall: Merging forward into the first array overwrites values that have not been compared; merge from the back when storage overlaps.

Pitfall: Losing list2’s head or tail during splicing makes the remainder unreachable; store both boundary pointers before assignment.

Pitfall: Off-by-one errors around n and y can retain or discard the wrong node; draw a small pointer diagram and test adjacent positions.

Practice these

The practice cards below cover the canonical variants—solve all of them and time yourself.

Practice questions

Related concepts