1. Title Description

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.Copy the code

The sample

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

Second, train of thought analysis

I don’t know if you’re like me, but when you see this problem for the first time, it’s just different from what we’ve done before. But if we think about it a little bit, it’s just to see how we feel about the basic operations of a linked list, we just have to write functions or classes that fit the requirements. So let me write a singly linked list here

AC code

Var MyLinkedList = function() {this.head=null this.rear=null this.len=0}; var MyLinkedList = function() {this.head=null this.rear=null this.len=0}; Function ListNode(val) {this.val = val; function ListNode(val) {this.val = val; this.next = next; } // Get the value of the index node in the list. If the index is invalid, -1 is returned. MyLinkedList.prototype.get = function(index) { if(index<0||index>this.len-1) return -1 var node=this.head while(index-->0){ if(node.next==null) return -1 node=node.next } return node.val }; MyLinkedList.prototype.addAtHead = function(val) { var node=new ListNode(val) if(this.head==null) this.rear=node else node.next=this.head this.head=node this.len++ }; MyLinkedList.prototype.addAtTail = function(val) { var node=new ListNode(val) if(this.head==null) this.head=node else this.rear.next=node this.rear=node this.len++ }; MyLinkedList.prototype.addAtIndex = function(index, val) { if(index<=0) return this.addAtHead(val) if(this.len<index) return if(index==this.len) return this.addAtTail(val) var node=this.head while(index-->1){ node=node.next } var newnode=new ListNode(val) newnode.next=node.next node.next=newnode this.len++ }; MyLinkedList.prototype.deleteAtIndex = function(index) { if(index<0||index>this.len-1||this.len==0) return if(index==0){  this.head=this.head.next this.len-- return } var node=this.head var myindex=index while(index-->1){ node=node.next } if(myindex==(this.len-1)){ this.rear=node } node.next=node.next.next this.len-- };Copy the code
Constructor () {this.arr = []; // Constructor () {this.arr = []; } get(index) { if (index < 0 || index >= this.arr.length) return -1; return this.arr[index]; } addAtHead(val) { this.arr.unshift(val); } addAtTail(val) { this.arr.push(val); } addAtIndex(index, val) { if (index < 0) { this.arr.push(val); return; } if (index > this.arr.length) { return; } this.arr.splice(index, 0, val); } deleteAtIndex(index) { if (index >= 0 && index < this.arr.length) this.arr.splice(index, 1); }}Copy the code

Four,

I added the array version later, which was a bit of a cheat.

In fact, when we write it out, we find it is not very difficult, but we need to be careful, and understand the structure of the linked list

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign