Likou 707 - Design Linked List - Linked List

Title description

Design the implementation of linked lists.You can choose to use a singly or doubly linked list.A node in a singly linked list should have two properties: val and next.val is the value of the current node and next is a pointer/reference to the next node.If you want to use a doubly linked list, you also need an attribute prev to indicate the previous node in the linked list.Assume that all nodes in the linked list are 0-indexed.

Implement these functions in the linked list class:

get(index): Get the value of the index-th node in the linked list.Returns -1 if the index is invalid.
addAtHead(val): Add a node with a value of val before the first element of the linked list.After insertion, the new node will be the first node of the linked list.
addAtTail(val): Append the node with value val to the last element of the linked list.
addAtIndex(index,val): Add a node with a value of val before the index-th node in the linked list.If index is equal to 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 of the linked list, the node will not be inserted.If index is less than 0, insert the node at the head.
deleteAtIndex(index): If the index index is valid, delete the index-th node in the linked list.

Solution ideas

AddAtTail(val) and addAtHead(val) can both be implemented by the function addAtIndex(index,val).

Input and output example

Code

class ListNode{int val;ListNode next;ListNode(){}ListNode(int val){this.val = val;}}class MyLinkedList {int size;ListNode head;public MyLinkedList() {size = 0;head = new ListNode(0);}//Get the index-th nodepublic int get(int index) {if(index < 0 || index >= size){return -1;}ListNode cur = head;for(int i = 0; i <= index; i++){cur = cur.next;}return cur.val;}//Insert a node at the top of the linked listpublic void addAtHead(int val) {addAtIndex(0,val);}//Insert a node at the last position of the linked listpublic void addAtTail(int val) {addAtIndex(size,val);}//Insert node val at indexpublic void addAtIndex(int ​​index, int val) {if(index > size) return;if(index < 0) index = 0;size++;ListNode pre = head;for(int i = 0; i < index; i++){pre = pre.next;}ListNode toAdd = new ListNode(val);toAdd.next = pre.next;pre.next = toAdd;}// delete the index nodepublic void deleteAtIndex(int ​​index) {if(index < 0 || index >= size) return;ListNode pre = head;size--;for(int i = 0; i < index; i++){pre = pre.next;}pre.next = pre.next.next;}}