Code Caprice Algorithm Training Camp Day 3 | 203. Remove Linked List Elements , 707. Design Linked Lists , 206. Reverse Linked Lists

Linked List Basics

Linked list node definition:

Single list

struct ListNode {
    int val;  //Store elements on nodes
    ListNode *next;  //pointer to the next node
    ListNode(int x) : val(x), next(nullptr) {}  //node constructor
};

Note: Although C++ will generate a constructor by default without writing this constructor, the constructor generated by C++ by default will not initialize any member variables!

The time complexity of adding and deleting the linked list is smaller than that of the array, which is O(1), but the premise of adding or deleting is to find the previous node of the operation node, and the time complexity of searching in the linked list is O(n).

	Insertion/deletion (time complexity)	query (time complexity)	scenes to be used
array	O(n)	O(1)	The amount of data is fixed, frequent queries, less additions and deletions
linked list	O(1)	O(n)	The amount of data is not fixed, frequent additions and deletions, and fewer queries

LeetCode 203 Remove Linked List Elements

Topic link: 203. Remove linked list elements

Idea: The removal operation of the linked list is to make the node next pointer directly point to the next node, but the original node still exists, and the memory needs to be released!

Due to the particularity of the linked list, when deleting the head node, there will be two processing methods:

1. Use the original linked list directly to delete
2. Set a virtual head node, and then delete

Method 1: directly use the original linked list to delete (directly move the head node backward one bit)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //delete head node
        while(head != NULL && head->val == val) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
        
        //remove non-head nodes
        ListNode* cur = head;
        while(cur != NULL && cur->next!= NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else {
                cur = cur->next;
            }
        }
        return head;
  }
};

Method 2: Set a virtual head node, and then perform a deletion operation (the same as other node operations)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);  //Set up a virtual head node
        dummyHead->next = head;  //Point the virtual head node to head, which is convenient for later operations
        ListNode* cur = dummtHead;
        while(cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

Note: When using this method to return the head node, remember to return dummyNode->next;, this is the new head node

LeetCode 707 Question Design Linked List

Topic link: 707. Design Linked List

Implement these functions in the linked list class:

• get(index): Get the value of the index node in the linked list. Returns -1 if the index is invalid.
• addAtHead(val): Add a node with value 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 the value val before the index 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.

class MyLinkedList {
public:
    //Define the 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);  //Define the virtual head node here
        _size = 0;
    };
    
     //Get the value of the index node, if the index is an illegal value, return -1 directly
    int get(int index) {
        if(index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    //Add a node at the front of the linked list
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    
    //Add a node at the end of the linked list
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    
    // Insert a new node before the index-th node, for example, if the index is 0, then the newly inserted node is the new head node of the linked list.
    // If index is equal to the length of the linked list, it means that the newly inserted node is the tail node of the linked list
    // If index is greater than the length of the linked list, return empty
    // If index is less than 0, insert the node at the head
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    //Delete the index node, if the index is greater than the length of the linked list, return directly, the index starts from 0
    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--;
    }
    private:
    int _size;
    LinkedNode* _dummyHead;
};

LeetCode 206 question reverse linked list

Topic link: 206. Reverse Linked List

Idea: Define a cur pointer to point to the head node, define a pre pointer to initialize to null, use tmp to continuously save cur->next, then cur->next points to pre, and pre moves backward until cur points to NULL.

double pointer method

class Solution {
public:
   ListNode* reverseList(ListNode* head) {
       ListNode* temp;
       ListNode* cur = head;
       ListNode* pre = NULL;
       while(cur) {
           temp = cur->next;
           cur->next = pre;
           pre = cur;
           cur = temp;
       }
       return pre;
   }
};

recursive method

class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL, head);
    }
};

Flip pointer from back to front

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // edge condition judgment
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        // Recursive call, flip the linked list starting from the second node
        ListNode *last = reverseList(head->next);
        // Flip the direction of the head node and the second node
        head->next->next = head;
        // At this time, the head node is the tail node, and next points to NULL
        head->next = NULL;
        return last;
    }
};