[B] [C] [D]

Design the implementation of linked lists. You can choose to use single or double linked lists. Nodes in a singly linked list should have two attributes: val and next. Val is the value of the current node and next is a pointer/reference to the next node. If you are using a bidirectional linked list, you also need an attribute prev to indicate the last node in the list. Assume that all nodes in the list are 0-index.

Implement these functions in the linked list class:

  • Get (index) : Get the first digit in the listindexThe value of a node. Returns if the index is invalid- 1.
  • AddAtHead (val) : Adds a value before the first element of the listvalThe node. After insertion, the new node becomes the first node in the linked list.
  • AddAtTail (val) : sets the value tovalAppends the node to the last element of the list.
  • AddAtIndex (index,val) : the first digit in the linked listindexThe value added before the node isvalThe node. ifindexEqual to the length of the list, the node is appended to the end of the list. ifindexGreater than the list length, nodes will not be inserted. ifindexLess than 0, insert the node in the header.
  • DeleteAtIndex (index) : if the indexindexValid, delete the first in the linked listindexA node.

Example:

MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); LinkedList. AddAtIndex (1, 2); // change the list to 1-> 2-> 3 linkedList.get(1); // Return 2 linkedList.deleteatIndex (1); // Now the list is 1-> 3 linkedList.get(1); / / return 3Copy the code

Tip:

  • allvalValues are[1, 1000]Within.
  • The number of operations will be in[1, 1000]Within.
  • Please do not use the built-in LinkedList library.

In this case, we can use an array to create a linked list. The array itself has an index property.

If you want to create a linked list, you have to create a linked list. My personal view is this:

It is certainly possible to simulate a linked list through objects, but it is nothing more than to record the length of the linked list. When you need to find the corresponding node, you can record the subscript through a variable, and then look down layer by layer until you find the corresponding index node.

There’s nothing special here, and we have arrays ready to use, so for the sake of the problem, there’s no need to implement a linked list, right

If I just want to simulate a linked list with objects, you can write it by hand, and that’s perfectly fine.

Here my problem is solved by using the array directly, the code is as follows:

var MyLinkedList = function() { this.list = []; }; /** * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function(index) { if(index<0 || index>=this.list.length) return -1; return this.list[index] }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function(val) { this.list.unshift(val);  }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function(val) { this.list.push(val); }; /** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if(index<0) this.addAtHead(val) else if(index===this.list.length) this.addAtTail(val) else if(index>this.list.length) return; else this.list.splice(index,0,val) }; /** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { if(index<0 || index>=this.list.length) return; this.list.splice(index,1) };Copy the code

At this point we are done with leetcode-707-Design linked list

If you have any questions or suggestions, please leave a comment!