Leetcode -- linked list

Linked list ： Single chain list 、 Double linked list 、 Circular linked list .

The difference between linked list and array ：

	add to / Delete	lookup	Applicable scenario
Array	O(n）	O(1)	The data is fixed , Search frequently , Less additions and deletions
Linked list	O(1)	O(n)	Data is not fixed , Add and delete frequently , Search less

203 Remove linked list elements

c++ Use the linked list to delete the elements delete Memory space of this element

Method 1 ： If the header node is an element that needs to be deleted , Need to put head = head->next

 ListNode* removeElements(ListNode* head, int val) {
        //val Is the head node element 
        while (head != NULL && head->val == val)
        {
            ListNode* tmp = head;            
            head = head->next;
            delete tmp;
        }
        ListNode* p = head;
        //val Not a header node element  
        while(p != NULL && p->next != NULL){
            if(p->next->val == val){
                ListNode* tmp = p->next;
                p->next = p->next->next;
                delete tmp;
            }else{
                p = p->next;
            }
        }
        return head;
}

Method 2 ： Set up a virtual head node ( It needs to be initialized ), Let the virtual head node next = head, Finally, remember to let head = Of the virtual head node next, Then delete the virtual head node

ListNode* removeElements(ListNode* head, int val) {
        // Set up a virtual head node 
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* p = dummyHead;  //p Is the currently accessed node 
        while(p->next != NULL){
            if(p->next->val == val){
                ListNode* tmp = p->next;
                p->next = p->next->next;
                delete tmp;
            }else{
                p = p->next;
            }
        }
        // Finally, delete the set virtual head node 
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }

707 Design the list

For array traversal, you only need to know its length , The length of the linked list is unknown , You can only find one node at a time , Until... Of a node next = null

class MyLinkedList {
public:
    //  Define linked list node structure 
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    //  Initialize linked list 
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); //  The head node defined here   It's a virtual head node , Instead of the real chain header node 
        _size = 0;
    }

    //  Get to page No index Node values , If index It's illegal. It's returned directly -1,  Be careful index It's from 0 At the beginning , The first 0 The first node is the head node 
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ //  If --index  You're going to fall into a dead circle 
            cur = cur->next;
        }
        return cur->val;
    }

    //  Insert a node at the front of the linked list , After insertion , The newly inserted node is the new head node of the linked list 
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    //  Add a node to the last side of the list 
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    //  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 
    void addAtIndex(int index, int val) {
        if (index > _size) {
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    //  Delete the first index Nodes , If index  Greater than or equal to the length of the linked list , direct return, Be careful index It's from 0 At the beginning 
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }

    //  Print linked list 
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

206 Reverse a linked list

Double finger needling ： Definition cur The pointer points to the head node ,pre The pointer is initialized to null, Record tmp = cur->next and cur->next = pre, to update tmp and cur.

ListNode* reverseList(ListNode* head){
    ListNode* cur = head;
    ListNode* pre = nullptr;
    ListNode* tmp;
    while(cur){
        tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
} 

24 Two or two exchange nodes in a linked list

ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        while(cur->next != nullptr && cur->next->next != nullptr){
            ListNode* tmp1 = cur->next;
            ListNode* tmp2 = cur->next->next->next;
            
            cur->next = cur->next->next;
            cur->next->next = tmp1;
            cur->next->next->next = tmp2;

            cur = cur->next->next;
        }
        return dummyhead->next;
    }

19 Delete the last from the list n Nodes

 ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        //fast The pointer moves first n Step 
        while (n-- && fast->next != nullptr){
            fast = fast->next;
        }
        // fast One more step ahead of time , Because we need to make slow Point to the previous node of the deleted node 
        fast = fast->next;
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }

142 Link list find ring

 ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast!= NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }