LeetCode: Design Linked List Solution

Implementation

1var Node = function (val) {
2  this.val = val
3  this.next = null
4}
5
6/**
7 * Initialize your data structure here.
8 */
9var MyLinkedList = function () {
10  this.head = null
11  this.size = 0
12}
13
14/**
15 * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
16 * @param {number} index
17 * @return {number}
18 */
19MyLinkedList.prototype.get = function (index) {
20  if (index < 0 || index >= this.size || this.head === null) {
21    return -1
22  }
23
24  let curr = this.head
25  while (index--) {
26    curr = curr.next
27  }
28
29  return curr.val
30}
31
32/**
33 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
34 * @param {number} val
35 * @return {void}
36 */
37MyLinkedList.prototype.addAtHead = function (val) {
38  const node = new Node(val)
39  node.next = this.head
40  this.head = node
41  this.size++
42}
43
44/**
45 * Append a node of value val to the last element of the linked list.
46 * @param {number} val
47 * @return {void}
48 */
49MyLinkedList.prototype.addAtTail = function (val) {
50  if (this.head === null) {
51    this.addAtHead(val)
52    return
53  }
54
55  const node = new Node(val)
56  let curr = this.head
57  while (curr.next !== null) {
58    curr = curr.next
59  }
60  curr.next = node
61  this.size++
62}
63
64/**
65 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
66 * @param {number} index
67 * @param {number} val
68 * @return {void}
69 */
70MyLinkedList.prototype.addAtIndex = function (index, val) {
71  if (index === 0) {
72    this.addAtHead(val)
73    return
74  }
75  if (index === this.size) {
76    this.addAtTail(val)
77    return
78  }
79  if (index < 0 || index > this.size) {
80    return
81  }
82
83  const node = new Node(val)
84  let curr = this.head
85  while (index - 1) {
86    curr = curr.next
87    index--
88  }
89  node.next = curr.next
90  curr.next = node
91  this.size++
92}
93
94/**
95 * Delete the index-th node in the linked list, if the index is valid.
96 * @param {number} index
97 * @return {void}
98 */
99MyLinkedList.prototype.deleteAtIndex = function (index) {
100  if (index < 0 || index >= this.size) {
101    return
102  }
103
104  let curr = this.head
105  if (index === 0) {
106    this.head = curr.next
107  } else {
108    while (index - 1) {
109      curr = curr.next
110      index--
111    }
112    curr.next = curr.next.next
113  }
114  this.size--
115}
116
117/**
118 * Your MyLinkedList object will be instantiated and called as such:
119 * var obj = new MyLinkedList()
120 * var param_1 = obj.get(index)
121 * obj.addAtHead(val)
122 * obj.addAtTail(val)
123 * obj.addAtIndex(index,val)
124 * obj.deleteAtIndex(index)
125 */

Running test cases locally

1const methods = [
2  "addAtHead",
3  "addAtTail",
4  "addAtIndex",
5  "get",
6  "deleteAtIndex",
7  "get",
8]
9const params = [[1], [3], [1, 2], [1], [1], [1]]
10var obj = new MyLinkedList()
11
12for (let i = 0; i < methods.length; i++) {
13  console.log(methods[i], params[i])
14  console.log(obj[methods[i]].apply(obj, params[i]))
15
16  const arr = []
17  let curr = obj.head
18  while (curr) {
19    arr.push(curr.val)
20    curr = curr.next
21  }
22  console.log("//", arr)
23  console.log()
24}