Problems

Q1: Reverse Linked List

Reverse 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* reverseList(ListNode* head) {
        // handle first Node
        if(head == nullptr || head -> next == nullptr) return head;

        ListNode* prev = head;
        ListNode* cur = head -> next;
        ListNode* temp = head -> next -> next;
        prev -> next = nullptr;

        // handle middle Nodes
        while(temp != nullptr) {
            cur -> next = prev;
            prev = cur;
            cur = temp;
            temp = temp -> next;
        }

        // handle last Node
        cur -> next = prev;
        head = cur;
        return head;
    }
};

Q2: Middle Of Linked List

Approach # 01

int getLength(Node* head){
    int cnt = 0;
    while(head != NULL){
        cnt++;
        head = head->next;
    }
    return cnt;
}
Node *findMiddle(Node *head) {
    int mid = getLength(head)/2;
    //int cnt = 0;
    
    while(mid-- != 0) // (count++ < mid)
        head = head->next;

    return head; // returning pointer pointing to the middle of the list
} 

i/p = [1,2,3,4,5]
o/p = [3,4,5]


T.C = O(n) + O(n/2)
    = O(n) + O(n)
    = 2 O(n)
    = O(n)

Q3: Sort 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:
    void getSize(ListNode* head, int& size){
        ListNode* temp = head;
        int i = 0;
        while(temp != nullptr){
            temp = temp -> next;
            i++;
        }
        size = i;
    }
    ListNode* sortList(ListNode* head) {
        int size;
        getSize(head, size);
        for(int i = 1; i < size;i++) {
            ListNode* prev = nullptr;
            ListNode* cur = head;
            ListNode* nxt = cur -> next;
            bool isSorted = true;
            for(int j = 0; j < size-i; j++) {
                
                if(cur -> val > nxt -> val){
                    cur -> next = nxt -> next;
                    nxt -> next = cur;
                    isSorted =false;
                    if(prev != nullptr) prev -> next = nxt;
                    else head = nxt;

                    cur = nxt;
                    nxt = nxt -> next;
                }
                prev = cur;
                cur = cur -> next;
                nxt = nxt -> next;
            }
            if(isSorted) break;
        }
        return head;
    }
};

Q4: Remove Duplicates from Sorted List

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != nullptr) {
            if(prev != nullptr && cur -> val == prev -> val) {
                prev -> next = cur -> next;
                ListNode* temp = cur;
                cur = cur -> next;
                delete temp;
                continue;
            }
            prev = cur;
            cur = cur -> next;
        }
        return head;
    }
};

Q5: Remove Duplicates from Sorted List II

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head -> next == NULL) return head;
        
        ListNode* prev = NULL;
        ListNode* cur = head;
        ListNode* nxt = head -> next;
        
        bool isFirstElemDup = false;

        if(cur -> val == nxt -> val) isFirstElemDup = true;
        
        while(nxt != NULL) {
            bool isDup = false;

            if(cur -> val == nxt -> val) {
                isDup = true;
                recheck:
                while(nxt != NULL && nxt -> val == cur -> val) {
                    cur = nxt;
                    nxt = nxt -> next;
                }
                if(nxt != NULL) {
                    if (nxt -> next != NULL && nxt -> next -> val == cur -> next -> val) {
                        cur = nxt;
                        nxt = nxt -> next;
                        goto recheck;
                    }
                }
            }
            if(isFirstElemDup) {
                prev = head = nxt;
                isFirstElemDup = false;
            }
            else if(isDup) prev -> next = nxt;
            
            if(!isDup) prev = cur;

            else prev = nxt;
            
            cur = nxt;

            if(nxt != NULL) nxt = nxt -> next;
        }
        return head;
    }
};

Q6: 148. Sort 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* sortList(ListNode* head) {
        ListNode* t1 = head;
        while(t1 != nullptr){ 
            ListNode* t3;
            ListNode* t2 = t1 -> next;
            int curVal = t1 -> val;
            bool isFind = false;
            while(t2 != nullptr) {
                if(t2 -> val < curVal) {
                    curVal = t2 -> val;
                    t3 = t2;
                    isFind = true;
                }
                t2 = t2 -> next;
            }
            if(isFind)
                swap(t1 -> val, t3 -> val);
            t1 = t1 -> next;
        }
        return head;

    }
};

Q7: 19. Remove Nth Node From End of List

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return head;
        if(head -> next == nullptr && n == 1) {
            head = nullptr;
            return head;
        }
        int count = 0;
        ListNode* t1 = head;
        while(t1 != nullptr) {
            count++;
            t1 = t1 -> next;
        }

        ListNode* t2 = head;

        while(count > n ) {
            count--;
            t1 = t2;
            t2 = t2 -> next;
        }
        
        // for first node
        if(t1 == nullptr) {
            head = head -> next;
            t1 = t2 = nullptr;
            return head;
        }

        // for middle and last node
        t1 -> next = t2 -> next;
        return head;
    }
};

Q8: Rotate List

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == NULL || head -> next == NULL || k == 0) return head;

        ListNode* prev = head;
        ListNode* cur = head;
        int n = 0;

        while(cur != nullptr) {
            cur = cur -> next;
            n++;
        }

        if (k % n == 0) return head; // 10,000 % 5 = 0

        if(n < k) k %= n; // 5 < 98553 --> k = 98553 % 5 = 3 steps

        cur = head;

        for(int i = n; i > k; i--) {
            prev = cur;
            cur = cur -> next;
        }

        ListNode* curHead = cur;

        while(cur -> next != nullptr) {
            cur = cur -> next;
        }

        prev -> next = nullptr;
        cur -> next = head;
        head = curHead;
        return head;
    }
};

Q9: Reverse Nodes in k-Group

class Solution {
public:

    ListNode* reverseKGroup(ListNode* head, int k) {
        
        stack<ListNode*> st;
        ListNode* temp = nullptr;
        ListNode* tempHead;
        ListNode* t1 = head;
        int count = 0;
        
        while(t1 != nullptr) {
            
            tempHead = t1;
            while(count < k && t1 != nullptr) {

                st.push(t1); 
                t1 = t1 -> next;
                count++;
            }

            if(count < k) return head;

            while(!st.empty()) {

                if(temp == nullptr) 
                    temp = head = st.top();

                else {
                    temp -> next = st.top();
                    temp = temp -> next;
                }
                st.pop();
            }
            tempHead -> next = t1;
            count = 0;
        }
        return head;
    }
};