Skip to content

707. Design Linked List

On LeetCode ->

Problem

Implement MyLinkedList, a zero-indexed linked list supporting:

  • get(index): return the value, or -1 for an invalid index.
  • addAtHead(val) and addAtTail(val): insert at either end.
  • addAtIndex(index, val): insert before index; allow index == length, but ignore larger indices.
  • deleteAtIndex(index): delete a valid index; otherwise do nothing.
Operation           State       Return
addAtHead(1)        [1]          None
addAtTail(3)        [1, 3]       None
addAtIndex(1, 2)    [1, 2, 3]    None
get(1)              [1, 2, 3]    2
deleteAtIndex(1)    [1, 3]       None
get(1)              [1, 3]       3

class MyLinkedList:
    def __init__(self):
        pass

    def get(self, index: int) -> int:
        pass

    def addAtHead(self, val: int) -> None:
        pass

    def addAtTail(self, val: int) -> None:
        pass

    def addAtIndex(self, index: int, val: int) -> None:
        pass

    def deleteAtIndex(self, index: int) -> None:
        pass

Key trick

Use a permanent dummy head to make every insertion/deletion a change to a predecessor's next; maintain a tail pointer for constant-time appending.

Trap

Insertion accepts index == length, but lookup/deletion do not; every operation must preserve the tail pointer, including transitions to and from an empty list.

Why is it interesting?

It tests pointer invariants and boundary handling rather than a complicated algorithm.

Python solution

class MyLinkedList:
    class Node:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = self.Node()  # Permanent dummy; not a list element.
        self.tail = self.head   # Empty lists end at the dummy.
        self.length = 0

    def _prev(self, index: int):
        # Caller guarantees 0 <= index <= length.
        if index == self.length:
            return self.tail

        node = self.head
        for _ in range(index):
            node = node.next
        return node

    def get(self, index: int) -> int:
        if not 0 <= index < self.length:
            return -1
        return self._prev(index).next.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.length, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if not 0 <= index <= self.length:
            return

        prev = self._prev(index)
        node = self.Node(val, prev.next)
        prev.next = node

        if index == self.length:
            self.tail = node
        self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        if not 0 <= index < self.length:
            return

        prev = self._prev(index)
        node = prev.next
        prev.next = node.next

        if node is self.tail:
            self.tail = prev  # Becomes the dummy when deleting the sole node.
        self.length -= 1

Time: addAtHead and addAtTail take \(O(1)\); indexed operations take \(O(n)\) worst case. Insertion at index \(n\) and deletion at index \(0\) take \(O(1)\).

Space: \(O(n)\) storage, with \(O(1)\) auxiliary space per operation.

Comment on my solution

  • Your predecessor-based insertion/deletion approach is sound, and appending is already \(O(1)\).
  • addAtIndex never updates self.tail. Inserting into an empty list leaves it None; inserting at the end leaves it pointing to the previous last node.
  • Deleting the sole node leaves self.tail pointing to a temporary dummy rather than None. Your subsequent insertions sometimes repair this, but the empty-list invariant is broken.
# d . . . .
#   d
#   . . . .
#     d
#   . . . .
#       d
#   . . . .

# WRONG
# Runtime Error: 12/52 testcases passed
class MyLinkedList:
    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next = next

    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def get(self, index: int) -> int:
        if index >= self.length:
            return -1
        node = self.head
        for _ in range(index):
            node = node.next
        return node.val

    def addAtHead(self, val: int) -> None:
        self.head = self.Node(val, self.head)
        self.length += 1
        if self.length == 1:
            self.tail = self.head

    def addAtTail(self, val: int) -> None:
        tail = self.Node(val)
        self.length += 1
        if self.length == 1:
            self.head = tail
            self.tail = tail
        else:
            self.tail.next = tail
            self.tail = tail

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.length:
            return
        dummy = self.Node(0, self.head)
        node = dummy
        for _ in range(index):
            node = node.next
        nxt = node.next
        node.next = self.Node(val, nxt)

        self.head = dummy.next
        self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.length:
            return
        dummy = self.Node(0, self.head)
        node = dummy
        for _ in range(index):
            node = node.next
        node.next = node.next.next

        self.head = dummy.next
        if index == self.length - 1:
            self.tail = node
        self.length -= 1

# WORKS
# Written after reading AI comments
# I just had to add this to addAtTail()
#     if index == self.length - 1:
#         self.tail = node.next
class MyLinkedList:
    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next = next

    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def get(self, index: int) -> int:
        if index >= self.length:
            return -1
        node = self.head
        for _ in range(index):
            node = node.next
        return node.val

    def addAtHead(self, val: int) -> None:
        self.head = self.Node(val, self.head)
        self.length += 1
        if self.length == 1:
            self.tail = self.head

    def addAtTail(self, val: int) -> None:
        tail = self.Node(val)
        self.length += 1
        if self.length == 1:
            self.head = tail
            self.tail = tail
        else:
            self.tail.next = tail
            self.tail = tail

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.length:
            return
        dummy = self.Node(0, self.head)
        node = dummy
        for _ in range(index):
            node = node.next
        nxt = node.next
        node.next = self.Node(val, nxt)
        self.length += 1
        self.head = dummy.next
        if index == self.length - 1:
            self.tail = node.next


    def deleteAtIndex(self, index: int) -> None:
        if index >= self.length:
            return
        dummy = self.Node(0, self.head)
        node = dummy
        for _ in range(index):
            node = node.next
        node.next = node.next.next

        self.head = dummy.next
        if index == self.length - 1:
            self.tail = node
        self.length -= 1