Skip to content

707. Design Linked List

  • Time:
    • Constructor: $O(1)$
    • get(index: int): $O(\texttt{index})$
    • addAtHead(val: int): $O(1)$
    • addAtTail(val: int): $O(n)$`
  • Space: $O(n)$
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class MyLinkedList {
  struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

 public:
  int get(int index) {
    if (index < 0 || index >= length)
      return -1;
    ListNode* curr = dummy.next;
    for (int i = 0; i < index; ++i)
      curr = curr->next;
    return curr->val;
  }

  void addAtHead(int val) {
    ListNode* head = dummy.next;
    ListNode* node = new ListNode(val);
    node->next = head;
    dummy.next = node;
    ++length;
  }

  void addAtTail(int val) {
    ListNode* curr = &dummy;
    while (curr->next != nullptr)
      curr = curr->next;
    curr->next = new ListNode(val);
    ++length;
  }

  void addAtIndex(int index, int val) {
    if (index > length)
      return;
    ListNode* curr = &dummy;
    for (int i = 0; i < index; ++i)
      curr = curr->next;
    ListNode* cache = curr->next;
    ListNode* node = new ListNode(val);
    node->next = cache;
    curr->next = node;
    ++length;
  }

  void deleteAtIndex(int index) {
    if (index < 0 || index >= length)
      return;
    ListNode* curr = &dummy;
    for (int i = 0; i < index; ++i)
      curr = curr->next;
    ListNode* cache = curr->next;
    curr->next = cache->next;
    --length;
    delete cache;
  }

 private:
  int length = 0;
  ListNode dummy = ListNode(0);
};

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class MyLinkedList {
  private class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
      this.val = val;
      this.next = null;
    }
  }

  public int get(int index) {
    if (index < 0 || index >= length)
      return -1;
    ListNode curr = dummy.next;
    for (int i = 0; i < index; ++i)
      curr = curr.next;
    return curr.val;
  }

  public void addAtHead(int val) {
    ListNode head = dummy.next;
    ListNode node = new ListNode(val);
    node.next = head;
    dummy.next = node;
    ++length;
  }

  public void addAtTail(int val) {
    ListNode curr = dummy;
    while (curr.next != null)
      curr = curr.next;
    curr.next = new ListNode(val);
    ++length;
  }

  public void addAtIndex(int index, int val) {
    if (index > length)
      return;
    ListNode curr = dummy;
    for (int i = 0; i < index; ++i)
      curr = curr.next;
    ListNode cache = curr.next;
    ListNode node = new ListNode(val);
    node.next = cache;
    curr.next = node;
    ++length;
  }

  public void deleteAtIndex(int index) {
    if (index < 0 || index >= length)
      return;
    ListNode curr = dummy;
    for (int i = 0; i < index; ++i)
      curr = curr.next;
    ListNode cache = curr.next;
    curr.next = cache.next;
    --length;
  }

  int length = 0;
  ListNode dummy = new ListNode(0);
}

 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
48
49
50
51
52
53
54
55
from dataclasses import dataclass


@dataclass
class ListNode:
  val: int
  next: ListNode | None = None


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

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

  def addAtHead(self, val: int) -> None:
    curr = self.dummy.next
    self.dummy.next = ListNode(val)
    self.dummy.next.next = curr
    self.length += 1

  def addAtTail(self, val: int) -> None:
    curr = self.dummy
    while curr.next:
      curr = curr.next
    curr.next = ListNode(val)
    self.length += 1

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

  def deleteAtIndex(self, index: int) -> None:
    if index < 0 or index >= self.length:
      return
    curr = self.dummy
    for _ in range(index):
      curr = curr.next
    temp = curr.next
    curr.next = temp.next
    self.length -= 1