Reverse a linked list in group of given size
https://practice.geeksforgeeks.org/problems/reverse-a-linked-list-in-groups-of-given-size/1
class Solution { public: struct node *reverse(struct node *head, int k) { stack<node *> st; struct node *curr = head; struct node *prev = nullptr; while (curr != nullptr) { int ctr = 0; while (curr != nullptr && ctr < k) { st.push(curr); curr = curr->next; ctr++; } while (!st.empty()) { if (prev == nullptr) { prev = st.top(); head = prev; st.pop(); } else { prev->next = st.
Delete loop in a linked list
https://practice.geeksforgeeks.org/problems/remove-loop-in-linked-list/1
class Solution { public: void removeLoop(Node *head) { Node *hare = head, *tor = head; while (hare != nullptr && hare->next != nullptr && tor != nullptr) { tor = tor->next; hare = hare->next->next; if (hare == tor) { Node *ptr1 = tor, *ptr2 = tor; unsigned int k = 1; while (ptr1->next != ptr2) { ptr1 = ptr1->next; k++; } ptr1 = head; ptr2 = head; while (k--) ptr2 = ptr2->next; while (ptr2 !
Find the starting point of the loop
https://leetcode.com/problems/linked-list-cycle-ii/
class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == NULL || head->next == NULL) return NULL; ListNode *slow = head; ListNode *fast = head; bool isCycle = false; while (slow != NULL && fast != NULL) { slow = slow->next; if (fast->next == NULL) return NULL; fast = fast->next->next; if (slow == fast) { isCycle = true; break; } } if (!isCycle) return NULL; slow = head; while (slow !
Add 1 to a number represented as a linked list
https://practice.geeksforgeeks.org/problems/add-1-to-a-number-represented-as-linked-list/1
class Solution { Node *reverse(Node *head) { Node *prev = nullptr; Node *current = head; Node *next; while (current != nullptr) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } Node *addOneUtil(Node *head) { Node *ans = head; Node *temp, *prev = nullptr; int carry = 1, sum = 0; while (head != nullptr) { sum = carry + head->data; carry = (sum >= 10) ?
Add two numbers represented by linked lists
https://practice.geeksforgeeks.org/problems/add-two-numbers-represented-by-linked-lists/1
class Solution { Node *reverse(Node *head) { Node *prev = nullptr, *curr = head, *next = nullptr; while (curr != nullptr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } public: Node *addTwoLists(struct Node *first, struct Node *second) { first = reverse(first); second = reverse(second); int c = 0, sum = 0; Node *start = nullptr, *end = nullptr; while (first !
Check whether the singly linked list is a palindrome
https://practice.geeksforgeeks.org/problems/check-if-linked-list-is-pallindrome/1
class Solution { Node *reverseLL(Node *head) { Node *curr = head, *prev = nullptr, *next; while (curr != nullptr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } public: // Function to check whether the list is palindrome. bool isPalindrome(Node *head) { int ctr = 0; Node *slow = head, *fast = head; if (head == nullptr || head->next == nullptr) { return true; } while (slow !
Why is quicksort preferred for arrays while merge sort for linked lists?
Quicksort is also one of the efficient algorithms with the average time complexity of O(nlogn). But the worst-case time complexity is O(n^2). Also, variations of the quick sort like randomized quicksort are not efficient for the linked list because unlike arrays, random access in the linked list is not possible in O(1) time. If we sort the linked list using quicksort, we would end up using the head as a pivot element which may not be efficient in all scenarios.
Clone a linked list with next and random pointer
https://leetcode.com/problems/copy-list-with-random-pointer/
Inefficient
class Solution { public: Node *copyRandomList(Node *head) { map<Node *, Node *> mp; for (Node *c = head; c != nullptr; c = c->next) mp[c] = new Node(c->val); for (Node *c = head; c != nullptr; c = c->next) { mp[c]->next = mp[c->next]; mp[c]->random = mp[c->random]; } return mp[head]; } }; Optimised
class Solution { public: Node *copyRandomList(Node *head) { Node *iter = head; Node *front = head; while (iter !