Hack University
470/670

470. Design Linked List

Medium

Implement a linked list yourself — nodes, pointers, and all the index bookkeeping. Build a class MyLinkedList (0-indexed) supporting:

  • get(index) — return the value of the node at position index, or -1 if the index is invalid.
  • addAtHead(val) — insert a new node holding val before the first node.
  • addAtTail(val) — append a new node holding val after the last node.
  • addAtIndex(index, val) — insert a new node holding val so it ends up at position index. If index equals the current length, this is an append; if index is greater than the length, do nothing.
  • deleteAtIndex(index) — remove the node at position index if such a node exists; otherwise do nothing.

All stored values are between 0 and 1000, so -1 can only ever mean "invalid index". After the whole call sequence runs, the grader also reads your list front to back (via get) to check its final shape — so the pointer surgery has to be right, not just the returned values.

addAtIndex(1, 2) splices a node between 1 and 3Example 1: the new node takes over position 1. Its next points at the old occupant (3), and the predecessor (1) is rewired to point at it — exactly two pointer writes.
before: 1 → 313old pointerafter: 1 → 2 → 3123index 0index 1 (new)index 2two pointer writes:new.next = 31.next = new

Example 1:

Input: MyLinkedList(); addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1), get(1)

Output: [2, 3]; final list = [1, 3]

Explanation: After addAtHead(1) and addAtTail(3) the list is 1 → 3. addAtIndex(1, 2) splices a node between them: 1 → 2 → 3, so get(1) returns 2. deleteAtIndex(1) removes that node again, so get(1) now returns 3, and the final list is 1 → 3.

Example 2:

Input: MyLinkedList(); addAtIndex(0, 5), addAtIndex(3, 9), get(0), get(1), deleteAtIndex(4), addAtTail(7), deleteAtIndex(0)

Output: [5, -1]; final list = [7]

Explanation: addAtIndex(0, 5) on an empty list is legal (index equals the length, 0). addAtIndex(3, 9) is ignored — 3 exceeds the length 1. get(1) is -1 because only index 0 exists. deleteAtIndex(4) is a no-op, addAtTail(7) makes [5, 7], and deleteAtIndex(0) leaves [7].

Constraints:

  • 0 ≤ val ≤ 1000
  • 0 ≤ index (indices are never negative in the input)
  • At most 2000 operations in total
  • Do not use built-in list containers as the final answer — the point is the pointer manipulation (an array-backed version is a fine first draft)

Hints:

Every insert and delete at position i needs a handle on the node at position i − 1. Write one helper that walks from the front and returns that predecessor, and every operation becomes three lines.

Position 0 has no predecessor — unless you invent one. A sentinel (dummy) node that permanently sits before the real head makes addAtHead, addAtIndex(0, …) and deleteAtIndex(0) the same code path as every other index.

Track the length in a counter. Validity checks become simple comparisons: get/delete need index < length, insert allows index == length (append).

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1), get(1)

Expected output: [2, 3]; final list = [1, 3]