Design Linked List

src: https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1290/

Requirement

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object. int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.

void addAtHead(int val) 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.

void addAtTail(int val) Append a node of value val as the last element of the linked list.

void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.

void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.

var MyLinkedList = function () { this.head = null; }; /** * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function (index) { let currentNode = this.head; let currentIndex = 0; while (currentNode) { if (currentIndex === index) return currentNode.val; currentNode = currentNode.next; currentIndex++; } return -1; }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function (val) { const newHead = { val, next: this.head }; this.head = newHead; }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function (val) { if (!this.head) { this.addAtHead(val); return; } let currentNode = this.head; while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = { val, next: null }; }; /** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function (index, val) { let prevNode = null; let currentNode = this.head; let currentIndex = 0; if (index === 0) { this.addAtHead(val); return; } while (currentNode) { if (currentIndex === index) { const newNode = { val, next: currentNode }; prevNode.next = newNode; return; } prevNode = currentNode; currentNode = currentNode.next; currentIndex++; } if (currentIndex === index) { const newNode = { val, next: null }; prevNode.next = newNode; } }; /** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function (index) { let prevNode = null; let currentNode = this.head; let currentIndex = 0; if (index === 0) { this.head = this.head.next; return; } while (currentNode) { if (currentIndex === index) { prevNode.next = currentNode.next; } prevNode = currentNode; currentNode = currentNode.next; currentIndex++; } }; /** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */ function assert(expected, real, message = "") { if (expected === real) { console.log(`PASS: ${message}`); } else { console.log(`FAIL: ${message}`); throw new Error(`FAIL: ${message}` + JSON.stringify({ expected, real })); } } // test add/delete function test1() { var obj = new MyLinkedList(); obj.addAtHead(1); obj.addAtHead(2); obj.addAtHead(3); // 3->2-1 assert(obj.get(0), 3); obj.deleteAtIndex(0); assert(obj.get(0), 2); // 2-1 obj.deleteAtIndex(1); // 2 assert(obj.get(0), 2); assert(obj.get(1), -1); } function test5() { var obj = new MyLinkedList(); obj.addAtHead(7); obj.addAtHead(2); obj.addAtHead(1); // 1-2-7 obj.addAtIndex(3, 0); // 1-2-7-0 assert(0, obj.get(3)); obj.deleteAtIndex(2); // 1 2 0 assert(0, obj.get(2)); obj.addAtHead(6); // 6-1-2-0 assert(6, obj.get(0)); obj.addAtTail(4); // 6-1-2-0-4 assert(4, obj.get(4)); } function test6() { var obj = new MyLinkedList(); obj.addAtIndex(0, 10); obj.addAtIndex(0, 20); obj.addAtIndex(1, 30); // 20 30 10 assert(20, obj.get(0)); } function test7() { var obj = new MyLinkedList(); obj.addAtTail(1); assert(1, obj.get(0)); } test1(); test5(); test6(); test7();

1var MyLinkedList = function () {
2  this.head = null;
3};
4
5/**
6 * @param {number} index
7 * @return {number}
8 */
9MyLinkedList.prototype.get = function (index) {
10  let currentNode = this.head;
11  let currentIndex = 0;
12
13  while (currentNode) {
14    if (currentIndex === index) return currentNode.val;
15    currentNode = currentNode.next;
16    currentIndex++;
17  }
18
19  return -1;
20};
21
22/**
23 * @param {number} val
24 * @return {void}
25 */
26MyLinkedList.prototype.addAtHead = function (val) {
27  const newHead = { val, next: this.head };
28  this.head = newHead;
29};
30
31/**
32 * @param {number} val
33 * @return {void}
34 */
35MyLinkedList.prototype.addAtTail = function (val) {
36  if (!this.head) {
37    this.addAtHead(val);
38    return;
39  }
40  let currentNode = this.head;
41  while (currentNode.next) {
42    currentNode = currentNode.next;
43  }
44  currentNode.next = { val, next: null };
45};
46
47/**
48 * @param {number} index
49 * @param {number} val
50 * @return {void}
51 */
52MyLinkedList.prototype.addAtIndex = function (index, val) {
53  let prevNode = null;
54  let currentNode = this.head;
55  let currentIndex = 0;
56  if (index === 0) {
57    this.addAtHead(val);
58    return;
59  }
60  while (currentNode) {
61    if (currentIndex === index) {
62      const newNode = { val, next: currentNode };
63      prevNode.next = newNode;
64      return;
65    }
66    prevNode = currentNode;
67    currentNode = currentNode.next;
68    currentIndex++;
69  }
70
71  if (currentIndex === index) {
72    const newNode = { val, next: null };
73    prevNode.next = newNode;
74  }
75};
76
77/**
78 * @param {number} index
79 * @return {void}
80 */
81MyLinkedList.prototype.deleteAtIndex = function (index) {
82  let prevNode = null;
83  let currentNode = this.head;
84  let currentIndex = 0;
85  if (index === 0) {
86    this.head = this.head.next;
87    return;
88  }
89
90  while (currentNode) {
91    if (currentIndex === index) {
92      prevNode.next = currentNode.next;
93    }
94    prevNode = currentNode;
95    currentNode = currentNode.next;
96    currentIndex++;
97  }
98};
99
100/**
101 * Your MyLinkedList object will be instantiated and called as such:
102 * var obj = new MyLinkedList()
103 * var param_1 = obj.get(index)
104 * obj.addAtHead(val)
105 * obj.addAtTail(val)
106 * obj.addAtIndex(index,val)
107 * obj.deleteAtIndex(index)
108 */
109function assert(expected, real, message = "") {
110  if (expected === real) {
111    console.log(`PASS: ${message}`);
112  } else {
113    console.log(`FAIL: ${message}`);
114    throw new Error(`FAIL: ${message}` + JSON.stringify({ expected, real }));
115  }
116}
117
118// test add/delete
119function test1() {
120  var obj = new MyLinkedList();
121  obj.addAtHead(1);
122  obj.addAtHead(2);
123  obj.addAtHead(3);
124  // 3->2-1
125  assert(obj.get(0), 3);
126  obj.deleteAtIndex(0);
127  assert(obj.get(0), 2);
128
129  // 2-1
130  obj.deleteAtIndex(1);
131  // 2
132  assert(obj.get(0), 2);
133  assert(obj.get(1), -1);
134}
135
136function test5() {
137  var obj = new MyLinkedList();
138  obj.addAtHead(7);
139  obj.addAtHead(2);
140  obj.addAtHead(1);
141  // 1-2-7
142  obj.addAtIndex(3, 0);
143  // 1-2-7-0
144  assert(0, obj.get(3));
145
146  obj.deleteAtIndex(2);
147  // 1 2 0
148  assert(0, obj.get(2));
149  obj.addAtHead(6);
150  // 6-1-2-0
151  assert(6, obj.get(0));
152
153  obj.addAtTail(4);
154  // 6-1-2-0-4
155  assert(4, obj.get(4));
156}
157
158function test6() {
159  var obj = new MyLinkedList();
160  obj.addAtIndex(0, 10);
161  obj.addAtIndex(0, 20);
162  obj.addAtIndex(1, 30);
163  //  20 30 10
164  assert(20, obj.get(0));
165}
166
167function test7() {
168  var obj = new MyLinkedList();
169  obj.addAtTail(1);
170  assert(1, obj.get(0));
171}
172test1();
173test5();
174test6();
175
176test7();
177