JuniorCodeVery commonNot answered yet
Insert an element into a singly-linked list
Given a singly-linked list of Node, implement insertion at the front, at the back, and at an arbitrary 0-indexed position. Each function returns the (possibly new) head pointer.
Requirements:
- Front insertion must be O(1).
- Position-k insertion must walk only to the predecessor (O(k)).
- Handle insertion at position 0 (it changes the head) and an out-of-range position.
struct Node {
int val;
Node* next;
explicit Node(int v, Node* n = nullptr) : val(v), next(n) {}
};
Node* insertFront(Node* head, int val);
Node* insertBack(Node* head, int val);
Node* insertAt(Node* head, int val, int pos); // your code hereWrite the implementation.
Insertion at head is O(1): create a new node, set its next to the current head, update the head. Insertion at position k is O(k): traverse to the predecessor, splice in the new node. Insertion at tail without a tail pointer is O(n).
- ✗Forgetting to handle insertion at position 0 (head) separately
- ✗Walking one node too far — you need the node before the insertion point, not at it
- ✗Not updating the head pointer when inserting at position 0
- →How would you insert in sorted order into an already-sorted list?
- →What is the complexity of building a sorted linked list by repeated sorted insertion?
Contents
Task
Implement insert at front, back, and arbitrary position for a singly-linked list.
Key points
- Insert at front: O(1) — just redirect head.
- Insert at position k: walk to predecessor (k-1), splice in new node.
- Always handle position 0 separately as it changes the head.
Contents
