Linked list example _ merge linked list, reverse linked list

Single list

class MyLinkedList {
public:

    struct Node{
        int val;
        struct Node *next;
        Node(int x):val(x),next(NULL){};
    };

    int length;
    struct Node *head;

    MyLinkedList() {
        head = new Node(0);
        length = 0;
    }
    
    int get(int index) {
        if(index<0 || index>length-1) return -1;
        Node *p = head->next;
        int i = 0;
        while(p && i<index){
            p = p->next;
            i++;
        }
        if(!p || i>index){
            return -1;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        Node *p = head;
        Node *new_node = new Node(val);
        // new_node->val = val;
        new_node->next = p->next;
        p->next = new_node;
        length++;
    }
    
    void addAtTail(int val) {
        Node *p = head;
        Node *q = new Node(val);
        while(p->next){
            p = p->next;
        }
        p->next = q;
        length++;
    }
    
    void addAtIndex(int index, int val) {
        if(index<0 || index>length) return ;
        Node *new_node = new Node(val);
        Node *p = head;
        int i = 0;
        
        while(p && i<index){
            p = p->next;
            i++;
        }
        if(!p || i>index){
            return ;
        }
        new_node->next = p->next;
        p->next = new_node;
        length++;
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>=length) return ;
        Node *p = head;
        int i = 0;
        while(p && i<index){
            p = p->next;
            i++;
        }
        p->next = p->next->next;
        length--;
    }
};

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

linked list double pointer

circular linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Determine whether there is a ring: use the fast and slow pointer

The slow pointer takes one step at a time, and the fast pointer takes two steps each time. If they meet, it means that there is a ring. If one is empty, it means that there is no ring.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && slow && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

Determine if there is a ring

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        //find the meeting point
        while(fast && slow && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            //first encounter
            if(fast == slow) break;
        }
        //Determine if there is a ring
        if(!fast || !fast->next) return NULL;
        fast = head;//fast move to head node
        while(fast != slow){
            //one step at a time
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

Intersecting linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Concatenate two linked lists, compare them, and find the same node. is equivalent to:

After searching in A, go to B, and after B, go to A.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1=headA,*p2=headB;
        int cnt=0;
        while(p1&&p2){
            
            p1=p1->next;
            p2=p2->next;
            if(p1==p2){return p1;}
            if(cnt<2&&!p1){
                p1=headB;
                cnt++;
            }
            if(cnt<2&&!p2){
                p2=headA;
                cnt++;
            }
        }
        return NULL;
    }
};

Delete the N th node from the bottom of the linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Fast and slow pointers

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head;
        ListNode *slow = head;
        int i = 0;
        //fast moves forward n steps, when fast goes to the end, slow goes to the node to be deleted
        while(i < n){
            fast = fast->next;
            i++;
        }
        if(!fast) return head->next;//If fast is empty, it means that the head node is deleted
        //Find the previous node of the node to delete
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

(The head node is the first node)

reverse linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Method 1: Iteration

Iterate over nodes in original order and move them one by one to the head of the list

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        ListNode *p = head;
        ListNode *q = nullptr;
        while(p->next){
            q = p->next;
            p->next = q->next;
            q->next = head;
            head = q;
        }
        return head;
    }
};

Method 2: Stack

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        ListNode *p = head;
        stack<ListNode> s;
        while(p){
            s.push(p);
            p = p->next;
        }
        if(stack.empty()) return nullptr;
        ListNode *L = nullptr;
        ListNode *node = L;
        while(!s.empty()){
            ListNode *temp = s.top();
            node->next = temp;
            node = node->next;
            s.pop();
        }
        node->next = nullptr;
        return L->next;
    }
};

Method 3: Recursive

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //The linked list is empty, or the linked list has no tail node
        if(!head || !head->next) return head;
        //Save the next node of the current node
        ListNode *next = head->next;
        //Reverse the linked list starting from the next node of the current node
        //reverse is the linked list after the reverse, so the next after the reverse is the end node of the reverse
        ListNode *reverse = reverseList(next);
        //Hang the current node head after the tail node
        next->next = head;
        //The current node becomes the tail node 
        head->next = nullptr;
        return reverse;
    }
};

tail recursion

Although tail recursion will continue to push the stack, but because the value of the recursive function is finally returned, it will pop out of the stack at one time when returning, and it will not be so slow to pop out of the stack one by one.

Add nodes one by one to the front of the reversed linked list

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    
    ListNode* reverseListInt(ListNode *head,ListNode *newHead){
        if(!head) return newHead;
        ListNode *next = head->next;
        head->next = newHead;//The current node is connected to the pre-arranged linked list
        return reverseListInt(next,head);//The next node is the current node, and the current node is the head node of the already arranged linked list
    }
    ListNode* reverseList(ListNode* head) {
        return reverseListInt(head,nullptr);
    }
};

remove list element

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Method 1: Iteration

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) return head;
        ListNode *p = head;
        while(p && p->next){
            if(p->next->val == val){
                p->next = p->next->next;
                continue;
            }
            p = p->next;
        }
        if(head->val == val){
            head = head->next;
        }
        return head;
    }
};

Method 2: Recursion

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return nullptr;
        head->next = removeElements(head->next,val);
        //If there is val, delete and return head->next after removing a node, otherwise return head directly, that is, the entire sub-linked list
        return head->val == val ? head->next : head;
    }
};

parity linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Move two steps at a time, linking the same odd or even nodes

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }

        ListNode *odd = head;
        ListNode *even = head->next;
        ListNode *even_head = even;

        int i = 1;
        while(odd && even && odd->next && even->next){
            ListNode *target = even->next;
            even->next = even->next->next;
            even = even->next;
            target->next = odd->next;
            odd->next = target;
            odd = odd->next;
        }
        // odd->next = even_head;
        return head;
    }
};

Palindromic linked list

Method 1: Reverse the second half

Find the end of the linked list through the fast and slow pointer, reverse the second half, and compare whether the two linked lists are equal.

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head->next) return true;
        ListNode *slow = head;
        ListNode *fast = head;

        while(fast->next && fast->next->next){//The number of linked list nodes may be odd or even
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast->next && fast->next->next == nullptr){//When there are an even number of nodes, the end point is moved forward by one, and the linked list is separated from 1/2 and 1/2+1 to facilitate the comparison of the second half after the inversion. If it is an odd number, the linked list is moved from 1/2+  1 split, directly reverse the second half
            slow = slow->next;
        }
        ListNode* rev = reverse(slow);//reverse
        
        //Compare
        while(rev){
            if(head->val != rev->val) return false;
            head = head->next;
            rev = rev->next;
        }
        return true;

    }

    ListNode* reverse(ListNode *head){
        ListNode *prev = nullptr;
        
        while(head){
            ListNode *next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        // cout<<prev->val;
        return prev;
    }
};

Method 2: Stack

The node is pushed onto the stack and compared with the linked list elements when popped.

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<ListNode*> s;
        ListNode *p = head;
        while(p){
            s.push(p);
            p = p->next;
        }
        while(head){
            ListNode *temp = s.top();
            if(temp->val != head->val) return false;
            s.pop();
            head = head->next;
        }
        return true;
    }
};

Method 3: Recursive

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode *temp;
    bool isPalindrome(ListNode* head) {
        temp = head;
        return check(head);
    }

    bool check(ListNode* head){
        if(!head) return true;
        bool res =  check(head->next) && head->val == temp->val;
        temp = temp->next;
        return res;
    }
};

doubly linked list

class MyLinkedList {
public:
    struct Node{
        int val;
        Node *next;
        Node *prev;
        Node(int _val){
            val = _val;
            prev = NULL;
            next = NULL;
        }
    };
    Node *head;
    int size;
    MyLinkedList() {
        size = 0;
        head = new Node(0);
    }
    
    int get(int index) {
        if(index < 0 || index >= size) return -1;
        int i = 0;
        Node *p = head->next;
        while(i<index && p){
            p = p->next;
            i++;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        Node *p = new Node(val);
        if(head->next) head->next->prev= p;
        p->next = head->next;
        p->prev = head;
        head->next = p;
        size++;
    }
    
    void addAtTail(int val) {
        Node *p = new Node(val);
        Node *L = head;
        while(L->next){
            L = L->next;
        }
        L->next = p;
        p->prev = L;
        p->next = NULL;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index <= 0){
            addAtHead(val);
        }else if(index == size){
            addAtTail(val);
        }else if(index > size){
            return ;
        }else{
            Node *p = new Node(val);
            Node *L = head->next;
            int i = 0;
            while(i<index && L){
                L = L->next;
                i++;
            }
            if(!L || i>index){
                return ;
            }
            p->next = L;
            p->prev = L->prev;
            L->prev->next = p;
            L->prev = p;
            size++;
            }
    }
    
    void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return ;
        }
        Node *L = head->next;
        int i = 0;
        while(i<index && L){
            L = L->next;
            i++;
        }
        if(L->next){
            L->next->prev = L->prev;
            // L->prev->next = L->next;
        }
        L->prev->next = L->next;
        delete L;
        i++;
        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);
 */

other

Merge two sorted linked lists

method one

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *new_list = new ListNode();
        ListNode *head = new_list;
        while(list1 && list2){
            if(list1->val < list2->val){
                new_list->next = list1;
                list1 = list1->next;
            }else{
                new_list->next = list2;
                list2 = list2->next;
            }
            cout<<new_list->val<<endl;
            new_list = new_list->next;
        }
        new_list->next = list1 ? list1 : list2;
        return head->next;
    }
};

Method 2: Recursion

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        
        if(list1->val < list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list2->next,list1);
            return list2;
        }
    }
};

linked list summation

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0,nullptr);
        ListNode *new_list = head;
        int carry = 0;
        int sum = 0;
        while(l1 || l2 || carry){
            sum = 0;
            if(l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            ListNode *p = new ListNode();
            p->val = (sum + carry) % 10;
            new_list->next = p;
            new_list = new_list->next;
            carry = (sum + carry) / 10;  
        }
        return head->next;
    }
};

Tags: C++ data structure linked list leetcode

Posted by didgydont on Sun, 04 Sep 2022 22:16:44 +0530

Programs Team

Linked list example _ merge linked list, reverse linked list

Single list

linked list double pointer

circular linked list

Intersecting linked list

Delete the N th node from the bottom of the linked list

reverse linked list

remove list element

parity linked list

Palindromic linked list

doubly linked list

other

Merge two sorted linked lists

linked list summation

Hot Tags