#707

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Design Linked List

Implement a custom linked list supporting head, tail, index insertions, retrieval, and deletions efficiently with pointer manipulation.

linked list design

Problem Statement

Design and implement a linked list with core operations: adding a node at the head, tail, or a specific index, retrieving a value by index, and deleting a node by index. You may choose either a singly or doubly linked list, but pointer updates must be precise to maintain list integrity.

Each node in a singly linked list has a 'val' and a 'next' pointer. In a doubly linked list, nodes additionally have a 'prev' pointer. Indices are zero-based, and all operations must correctly update the surrounding nodes' pointers to maintain a consistent linked structure.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] Output [null, null, null, null, 2, null, 3]

Explanation MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3

Constraints

0 <= index, val <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Solution Approach

Choose Linked List Type

Decide between singly and doubly linked list. Singly is simpler and uses less memory, but doubly allows backward traversal and easier deletions at arbitrary indices. This choice affects pointer handling in all operations.

Implement Core Operations

Implement addAtHead, addAtTail, addAtIndex, get, and deleteAtIndex. Ensure each insertion or deletion updates neighboring pointers carefully. For get, traverse from head and respect index bounds to avoid null pointer errors.

Handle Edge Cases and Bounds

Check for invalid indices, empty list operations, and updating head/tail references. Forgetting these checks is the most common failure mode in pointer manipulation problems, leading to runtime exceptions or incorrect list state.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on list length: O(1) for head/tail insertion if tail pointer maintained, O(n) for get or index-based insert/delete. Space complexity is O(n) for storing nodes.

What Interviewers Usually Probe

Will ask about handling out-of-bound indices safely.
May probe your choice of singly versus doubly linked list and rationale.
Expect explanation of pointer updates for insertions and deletions.

Common Pitfalls or Variants

Common pitfalls

Failing to update neighboring node pointers after insertion or deletion.
Ignoring edge cases like empty list or inserting at index 0.
Mismanaging tail pointer when adding at the end in singly linked list.

Follow-up variants

Implement a circular linked list with similar operations.
Add a method to reverse the linked list in-place using pointer swaps.
Implement a linked list that tracks its size and returns it in O(1).

FAQ

What is the difference between singly and doubly linked lists for this problem?

Singly linked lists store only next pointers, saving space but making deletions at arbitrary indices slower. Doubly linked lists store prev pointers too, easing index deletions but using extra memory.

Can I use built-in LinkedList libraries for this problem?

No, the problem explicitly forbids built-in LinkedList libraries. You must implement node structures and pointer updates manually.

What should I do if addAtIndex receives an index equal to the list length?

Treat it as adding at the tail, updating tail pointers as needed. Ensure proper handling to avoid breaking the list.

How do I handle get or deleteAtIndex for invalid indices?

Return -1 for get and do nothing for deleteAtIndex when the index is out of bounds. Always validate indices before pointer operations.

Why is pointer manipulation the main pattern here?

Because every operation—insertions, deletions, retrievals—requires careful updates to next and prev references, which is the core challenge of linked list design.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode()
        self.cnt = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.cnt:
            return -1
        cur = self.dummy.next
        for _ in range(index):
            cur = cur.next
        return cur.val

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

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

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.cnt:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        pre.next = ListNode(val, pre.next)
        self.cnt += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.cnt:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        t = pre.next
        pre.next = t.next
        t.next = None
        self.cnt -= 1


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode()
        self.cnt = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.cnt:
            return -1
        cur = self.dummy.next
        for _ in range(index):
            cur = cur.next
        return cur.val

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

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

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.cnt:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        pre.next = ListNode(val, pre.next)
        self.cnt += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.cnt:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        t = pre.next
        pre.next = t.next
        t.next = None
        self.cnt -= 1


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Continue Practicing

#706 design hashmap #705 design hashset #641 design circular deque