Linked list - 707. Design linked list

1 Title Description

707. Design the list

Design the realization of linked list . You can choose to use single or double linked list . Nodes in a single chain table should have two properties ：val and next.val Is the value of the current node ,next Is a pointer to the next node / quote . If you want to use a two-way linked list , Then you need an attribute prev To indicate the last node in the list . Suppose that all nodes in the list are 0-index Of .
Implement these functions in the linked list class ：

• get(index)： Get the index Values of nodes . If the index is invalid , Then return to -1.
• addAtHead(val)： Add a value of... Before the first element of the list val The node of . After inserting , The new node will be the first node in the list .
• addAtTail(val)： Will be worth val To the last element of the list .
• addAtIndex(index,val)： In the list, the index The value added before nodes is val The node of . If index It's equal to the length of the list , Then the node will be attached to the end of the list . If index Greater than the length of the list , The node will not be inserted . If index Less than 0, Then insert the node in the head .
• deleteAtIndex(index)： If the index index It works , Delete the index Nodes .

2 Title Example

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); // Linked list becomes 1-> 2-> 3
linkedList.get(1); // return 2
linkedList.deleteAtIndex(1); // Now the list is 1-> 3
linkedList.get(1); // return 3

3 Topic tips

• all val It's worth it [1, 1000] within .
• The number of operations will be [1, 1000] within .
• Please don't use the built-in LinkedList library .

4 Ideas

This topic designs five interfaces of linked list ：

• Get the list number index The number of nodes
• Insert a node at the top of the list
• Insert a node on the last side of the list
• At the end of the list index Insert a node before each node
• Delete the first... Of the list index Nodes

It can be said that these five interfaces , Has covered the list of common operations , It's a very good topic to practice linked list operation

Two ways of linked list operation ：

• Directly use the original linked list to operate .
• Set a virtual head node to operate .
  

5 My answer

// Single chain list 
class ListNode {
    
    int val;
    ListNode next;
    ListNode(){
    }
    ListNode(int val) {
    
        this.val=val;
    }
}
class MyLinkedList {
    
    //size Stores the number of linked list elements 
    int size;
    // Virtual head node 
    ListNode head;

    // Initialize linked list 
    public MyLinkedList() {
    
        size = 0;
        head = new ListNode(0);
    }

    // For the first index The number of nodes 
    public int get(int index) {
    
        // If index illegal , return -1
        if (index < 0 || index >= size) {
    
            return -1;
        }
        ListNode currentNode = head;
        // Contains a virtual header node , So find number one  index+1  Nodes 
        for (int i = 0; i <= index; i++) {
    
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    // Insert a node at the front of the linked list 
    public void addAtHead(int val) {
    
        addAtIndex(0, val);
    }

    // Insert a node at the end of the linked list 
    public void addAtTail(int val) {
    
        addAtIndex(size, val);
    }

    //  In the  index  Insert a new node before two nodes , for example index by 0, Then the newly inserted node is the new head node of the linked list .
    //  If  index  It's equal to the length of the list , The newly inserted node is the tail node of the linked list 
    //  If  index  Greater than the length of the list , It returns null 
    public void addAtIndex(int index, int val) {
    
        if (index > size) {
    
            return;
        }
        if (index < 0) {
    
            index = 0;
        }
        size++;
        // Find the precursor to insert the node 
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
    
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    // Delete the first index Nodes 
    public void deleteAtIndex(int index) {
    
        if (index < 0 || index >= size) {
    
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
    
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

// Double linked list 
class MyLinkedList {
    
    class ListNode {
    
        int val;
        ListNode next,prev;
        ListNode(int x) {
    val = x;}
    }

    int size;
    ListNode head,tail;//Sentinel node

    /** Initialize your data structure here. */
    public MyLinkedList() {
    
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
    
        if(index < 0 || index >= size){
    return -1;}
        ListNode cur = head;

        //  By judgment  index < (size - 1) / 2  To determine whether to traverse from the beginning node or the end node , Increase of efficiency 
        if(index < (size - 1) / 2){
    
            for(int i = 0; i <= index; i++){
    
                cur = cur.next;
            }            
        }else{
    
            cur = tail;
            for(int i = 0; i <= size - index - 1; i++){
    
                cur = cur.prev;
            }
        }
        return cur.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. */
    public void addAtHead(int val) {
    
        ListNode cur = head;
        ListNode newNode = new ListNode(val);
        newNode.next = cur.next;
        cur.next.prev = newNode;
        cur.next = newNode;
        newNode.prev = cur;
        size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
    
        ListNode cur = tail;
        ListNode newNode = new ListNode(val);
        newNode.next = tail;
        newNode.prev = cur.prev;
        cur.prev.next = newNode;
        cur.prev = newNode;
        size++;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
    
        if(index > size){
    return;}
        if(index < 0){
    index = 0;}
        ListNode cur = head;
        for(int i = 0; i < index; i++){
    
            cur = cur.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = cur.next;
        cur.next.prev = newNode;
        newNode.prev = cur;
        cur.next = newNode;
        size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
    
        if(index >= size || index < 0){
    return;}
        ListNode cur = head;
        for(int i = 0; i < index; i++){
    
            cur = cur.next;
        }
        cur.next.next.prev = cur;
        cur.next = cur.next.next;
        size--;
    }
}

/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */