707. design linked list

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 .

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

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 .

a key ： Clear node p It should be from head Whether the node traverses to the target node or the previous node of the target node

1. C++:

class MyLinkedList {
private:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(): val(0), next(nullptr){}
        ListNode(int x): val(x), next(nullptr){}
        ListNode(int x, ListNode* next): val(x), next(next){}
    };
public:
    ListNode* head;
    int l = 0;
    MyLinkedList() {
        head = new ListNode();
    }
    
    int get(int index) {
        if (index>=l) return -1;
        ListNode* p = head;
        while(index>=0){
            p = p->next;
            index--;
        }
        return p->val;
    }
    void addAtHead(int val) {
        ListNode* p = head;
        ListNode* new_node = new ListNode(val, nullptr);
        new_node->next = p->next;
        p->next = new_node;
        l++;
    }
    void addAtTail(int val) {
        int index = l;
        ListNode* p = head;
        ListNode* new_node = new ListNode(val, nullptr);
        while(index--){
            p = p->next;
        }
        p->next = new_node;
        l++;
    }
    void addAtIndex(int index, int val) {
        if(index>l) return ;
        if(index<0) index=0;
        ListNode* p = head;
        ListNode* new_node = new ListNode(val, nullptr);
        while(index>0){
            p=p->next;
            index--;
        }
        new_node->next = p->next;
        p->next = new_node;
        l++;
    }
    void deleteAtIndex(int index) {
        if(index>=l | index<0) return ;
        ListNode* p = head;
        while(index>0){
            p=p->next;
            index--;
        }
        ListNode* temp =  p->next;
        p->next = temp->next;
        l--;
        delete temp;
    }
};

/**
 * 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);
 */

2. python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class MyLinkedList:

    def __init__(self):
        """ Initialize your data structure here. """
        self.size = 0
        self.head = ListNode(0)

    def get(self, index: int) -> int:
        """ Get the value of the index-th node in the linked list. If the index is invalid, return -1. """
        if index < self.size:
            p = self.head
            while index>=0:
                p = p.next
                index-=1
            return p.val
        else:
            return -1



    def addAtHead(self, val: int) -> None:
        """ 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. """
        self.addAtIndex(0,val)


    def addAtTail(self, val: int) -> None:
        """ Append a node of value val to the last element of the linked list. """
        self.addAtIndex(self.size,val)


    def addAtIndex(self, index: int, val: int) -> None:
        """ 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. """
        if index>self.size:
            return 
        new = ListNode(val)
        pre = self.head
        for _ in range(index):
            pre = pre.next
        new.next = pre.next
        pre.next = new
            
        
        self.size+=1

    def deleteAtIndex(self, index: int) -> None:
        """ Delete the index-th node in the linked list, if the index is valid. """
        if index<self.size:
            pre = self.head
            for _ in range(index):
                pre = pre.next
            post = pre.next.next
            pre.next = post
            self.size-=1




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