Topic describes

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) : Gets the value of the index node in the list. If the index is invalid, -1 is returned. AddAtHead (val) : Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the linked list. AddAtTail (val) : Appends a node with the value val to the last element of the list. AddAtIndex (index,val) : Adds a node with the value val before the index node in the linked list. If index is equal to the length of the list, the node is appended to the end of the list. If index is greater than the list length, no node will be inserted. If index is less than 0, insert the node in the header. DeleteAtIndex (index) : Deletes the index of the list if the index index is valid.

Analysis of the

We’re asked to implement a linked list class and implement its methods

Their thinking

The first is get:

If the index is less than 0 and greater than or equal to the length of the list, we consider it invalid because there are no nodes on the index.

So before searching, we deal with cases that are less than zero and return -1 if they are less than zero, and we also return -1 if there is no head.

Then, we declare a variable cur, point to head, find index with a count counter, and keep moving it around. If index is out of range, return -1, otherwise when count === index, we find the node we’re looking for

AddAtHead: We create a node and have it point to this.head. Next, and then point this.head to the new node we created

AddAtTail: We notice that we are dealing with the case where there is no head node, and then the other operation is the same as finding the element, we are looking for the tail node and have tail.next point to the new node we want to append

AddAtIndex:

Notice here they’re saying that anything less than zero goes to the head, so the first thing we’re going to make sure is, if we give our index < 0, we’re going to append nodes to the head.

Then look for the append location, same as above.

DeleteAtIndex:

No further elaboration, the same search process as above ~

code

var MyLinkedList = function () {
  this.head = null
}

/ * * *@param {number} index
 * @return {number}* /
MyLinkedList.prototype.get = function (index) {
  if (index < 0) {
    return -1
  }
  let count = 0
  let cur = this.head
  if(! cur)return -1

  while(index ! == count) { cur = cur.next count++if(! cur)return -1
  }

  if(index ! == count)return -1

  return cur.val
}

/ * * *@param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = { val, next: this.head }
  this.head = newNode
}

/ * * *@param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtTail = function (val) {
  let cur = this.head
  const newNode = { val, next: null }
  if(! cur) {this.head = newNode

    return
  }

  while (cur.next) {
    cur = cur.next
  }

  cur.next = newNode
}

/ * * *@param {number} index
 * @param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtIndex = function (index, val) {
  const newNode = { val, next: null }
  if (index <= 0) {
    newNode.next = this.head
    this.head = newNode
  }

  let count = 1
  let cur = this.head
  while(index ! == count) { count++if(! cur)return
    cur = cur.next
  }

  if (cur) {
    newNode.next = cur.next
    cur.next = newNode
  }
}

/ * * *@param {number} index
 * @return {void}* /
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0) {
    return
  }
  if (index === 0) {
    this.head = this.head.next
    return
  }

  let cur = this.head
  let count = 1
  while(index ! == count) { count++ cur = cur.nextif(! cur)return
  }

  cur.next = cur.next && cur.next.next
}

/** * 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) */
Copy the code

The complexity of the

Time: O(1), all operations are O(1) space: O(N), all data is to be stored