Reverse a linked list

Read more →

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.
Read more →

Detect loop in a linked list

Read more →

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 !
Read more →

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 !
Read more →

Remove duplicates in a sorted linked list

Read more →

Remove duplicates in a unsorted linked list

Read more →

Move the last element to front in a linked list

Read more →

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) ?
Read more →

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 !
Read more →

Intersection of two sorted linked list

Read more →

Intersection point of two linked lists

Read more →

Merge sort for linked lists

Read more →

Quicksort for linked lists

Read more →

Find the middle element of a linked list

Read more →

Check if a linked list is a circular linked list

Read more →

Split a circular linked list into two halves

Read more →

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 !
Read more →

Deletion from a circular linked list

Read more →

Reverse a doubly linked list

Read more →

Find pairs with a given sum in a DLL

Read more →

Count triplets in a sorted DLL whose sum is equal to given value X

Read more →

Sort a K sorted doubly linked list

Read more →

Rotate DLL by N nodes

Read more →

Rotate a doubly linked list in group of given size

Read more →

Can we reverse a linked list in less than O(n)?

Read more →

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.
Read more →

Flatten a linked list

Read more →

Sort a ll of 0s, 1s and 2s

Read more →

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 !
Read more →

Multiply 2 numbers represented by ll

Read more →

Delete nodes which have a greater value on right side

Read more →

Segregate even and odd nodes in a linked list

Read more →

Program for Nth node from the end of a linked list

Read more →

Find the first non-repeating character from a stream of characters

Read more →

Merge K sorted linked lists

Read more →