Linked-List

Problem Overview We are given the head of a singly linked list. We are given a node index n from the end. The goal is to remove the nth node from the end of the list. Constraints We have to do this in a single pass. Leetcode - Linked List Cycle Brute Force Approach Intuition We use a vector to keep track of the nodes and their indices. Once the traversal is finished, we calculate the node index from the start. Once we get that index, we remove that node. Code class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { vector<ListNode*> arr; ListNode* curr = head; while (curr) { arr.push_back(curr); curr = curr->next; } int nodeFromStart = arr.size() - n; if (nodeFromStart == 0) return head->next; if (nodeFromStart < arr.size()) arr[nodeFromStart - 1]->next = arr[nodeFromStart]->next; return head; } }; Why This Fails It usegs extra space O(n). The problem requires a constant space solution. Time and Space Complexity Time: O(n) Space: O(n) Optimal Approach We maintain two pointers similar to Floyd’s Tortoise and Hare technique. ...

Problem Overview We are given the heads of two singly linked lists. Both the linked lists are sorted in ascending order. Our goal is to merge the two lists into one sorted list and return the head. Leetcode - Linked List Cycle Example Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Brute Force Intuition We can simply traverse each list and push all values into a vector. Then we sort the vector. While iterating through the vector, we create a new linked list. Code class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { vector<int> values; while (list1) { values.push_back(list1->val); list1 = list1->next; } while (list2) { values.push_back(list2->val); list2 = list2->next; } sort(values.begin(), values.end()); ListNode dummy(0); ListNode* tail = &dummy; for (int val : values) { tail->next = new ListNode(val); tail = tail->next; } return dummy.next; } }; Why This Fails The lists were already sorted, and we are not taking advantage of that. It uses extra memory. Sorting adds unnecessary overhead. Time and Space Complexity Time: O(n log n) Space: O(n) Optimal Solution Instead of collecting all values, we directly compare nodes from both lists and attach the smaller one. ...

Problem Overview We are given the head of a singly linked list. We need to detect if a cycle is present in the list or not. Follow-up: Solve this in constant space. Leetcode - Linked List Cycle Example 3 → 2 → 0 → 4 ↑ ↓ └─────┘ As the last node 4 is linked back to 0, a cycle is present. Brute Force Intuition The idea is to store each node in a map. While iterating, if we encounter the same node again, there is a loop. ...

Problem Overview We are given the head of a singly linked list. We need to reverse the linked list. Follow-up: Solve it iteratively and recursively. Leetcode - Linked List Cycle Example Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Key Observations In a singly linked list, we can only traverse forward. Each node contains a pointer to the next node. Reversing the list means changing the direction of every next pointer. We must carefully store the next node before modifying links. Approach 1: Brute Force (Using Stack) Intuition Traverse the list. Push every node onto a stack. Pop nodes one by one to rebuild the list in reverse order. Code class Solution { public: ListNode* reverseList(ListNode* head) { if (!head) return NULL; stack<ListNode*> st; ListNode* curr = head; while (curr != NULL) { st.push(curr); curr = curr->next; } ListNode* newHead = st.top(); st.pop(); curr = newHead; while (!st.empty()) { curr->next = st.top(); st.pop(); curr = curr->next; } curr->next = NULL; return newHead; } }; Why It Is Not Optimal Uses extra data structure (stack). Requires additional memory. The problem can be solved in-place. Time and Space Complexity Time: O(n) Space: O(n) Approach 2: Three Pointer (Optimal Iterative) Intuition We maintain three pointers: ...