Linked List Manipulation, Coding Interview Pattern

Harsh Mishra - Sep 13 - - Dev Community

Linked List

A Linked List is a linear data structure consisting of nodes where each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists are dynamic and can easily grow or shrink in size by adding or removing elements without needing to shift other elements. This property makes linked lists particularly useful for implementing data structures such as stacks, queues, and others where the size can frequently change.

Reverse Linked List

This question is part of Leetcode problems, question no. 206.

Here’s the Solution class for the "Reverse Linked List" problem in C++:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;  // Initialize previous pointer as nullptr
        ListNode* current = head;  // Initialize current pointer to head

        while (current != nullptr) {
            ListNode* nextNode = current->next;  // Store next node
            current->next = prev;  // Reverse the current node's pointer
            prev = current;  // Move prev pointer one step forward
            current = nextNode;  // Move current pointer one step forward
        }

        return prev;  // Return the new head of the reversed list
    }
};
Enter fullscreen mode Exit fullscreen mode

Reverse Linked List II

This question is part of Leetcode problems, question no. 92.

Here’s the Solution class for the "Reverse Linked List II" problem in C++:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head || left == right) return head;

        ListNode* dummy = new ListNode(0);  // Dummy node to simplify edge cases
        dummy->next = head;
        ListNode* prev = dummy;

        // Move `prev` pointer to just before the `left` position
        for (int i = 1; i < left; ++i) {
            prev = prev->next;
        }

        ListNode* current = prev->next;  // `current` starts at `left`
        ListNode* nextNode;

        // Reverse the sublist between `left` and `right`
        for (int i = 0; i < right - left; ++i) {
            nextNode = current->next;
            current->next = nextNode->next;
            nextNode->next = prev->next;
            prev->next = nextNode;
        }

        return dummy->next;  // Return the updated list starting from the original head
    }
};
Enter fullscreen mode Exit fullscreen mode

Remove Nth Node From End of List

This question is part of Leetcode problems, question no. 19.

Here’s the Solution class for the "Remove Nth Node From End of List" problem in C++:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;

        for (int i = 1; i <= n + 1; ++i) {
            first = first->next;
        }

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

        second->next = second->next->next;
        return dummy->next;
    }
};
Enter fullscreen mode Exit fullscreen mode

Linked List Cycle

This question is part of Leetcode problems, question no. 141.

Here’s the Solution class for the "Linked List Cycle" problem in C++:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;

        ListNode* slow = head;
        ListNode* fast = head->next;

        while (slow != fast) {
            if (!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Linked List Cycle II

This question is part of Leetcode problems, question no. 142.

Here’s the Solution class for the "Linked List Cycle II" problem in C++:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        // Phase 1: Detect if there is a cycle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }

        // No cycle detected
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }

        // Phase 2: Find the start node of the cycle
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow; // Both pointers meet at the start of the cycle
    }
};
Enter fullscreen mode Exit fullscreen mode

Intersection of Two Linked Lists

This question is part of Leetcode problems, question no. 160.

Here’s the Solution class for the "Intersection of Two Linked Lists" problem in C++:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;

        ListNode* ptrA = headA;
        ListNode* ptrB = headB;

        // Traverse both lists. When a pointer reaches the end, redirect it to the head of the other list.
        // If they intersect, they will meet at the intersection node. If not, they will end up at the end of the lists together.
        while (ptrA != ptrB) {
            ptrA = ptrA ? ptrA->next : headB;
            ptrB = ptrB ? ptrB->next : headA;
        }

        return ptrA; // Either the intersection node or nullptr if no intersection
    }
};
Enter fullscreen mode Exit fullscreen mode

Add Two Numbers

This question is part of Leetcode problems, question no. 2.

Here’s the Solution class for the "Add Two Numbers" problem in C++:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;

        while (l1 || l2 || carry) {
            int sum = carry;

            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }

        return dummy->next;
    }
};
Enter fullscreen mode Exit fullscreen mode

Add Two Numbers II

This question is part of Leetcode problems, question no. 445.

Here’s the Solution class for the "Add Two Numbers II" problem in C++:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;

        // Push all values of l1 to stack s1
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }

        // Push all values of l2 to stack s2
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }

        ListNode* prev = nullptr;
        int carry = 0;

        // Process the stacks and build the result list
        while (!s1.empty() || !s2.empty() || carry) {
            int sum = carry;

            if (!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }

            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }

            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = prev;
            prev = node;
        }

        return prev;
    }
};
Enter fullscreen mode Exit fullscreen mode

Swap Nodes in Pairs

This question is part of Leetcode problems, question no. 24.

Here’s the Solution class for the "Swap Nodes in Pairs" problem in C++:

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = prev->next->next;

            // Swap the nodes
            first->next = second->next;
            second->next = first;
            prev->next = second;

            // Move prev pointer two nodes ahead
            prev = first;
        }

        return dummy->next;
    }
};
Enter fullscreen mode Exit fullscreen mode

Remove Linked List Elements

This question is part of Leetcode problems, question no. 203.

Here’s the Solution class for the "Remove Linked List Elements" problem in C++:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Remove leading nodes with the value 'val'
        while (head != nullptr && head->val == val) {
            head = head->next;
        }

        // If the list becomes empty, return nullptr
        if (head == nullptr) return head;

        // Initialize current pointer
        ListNode* current = head;

        // Traverse the list and remove nodes with the value 'val'
        while (current->next != nullptr) {
            if (current->next->val == val) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }

        return head;
    }
};
Enter fullscreen mode Exit fullscreen mode

Merge Two Sorted Lists

This question is part of Leetcode problems, question no. 21.

Here’s the Solution class for the "Merge Two Sorted Lists" problem in C++:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // Create a dummy node to simplify the merging process
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        // Merge the two lists while both have remaining nodes
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }

        // Append any remaining nodes from either list
        if (l1 != nullptr) {
            current->next = l1;
        } else {
            current->next = l2;
        }

        // Return the merged list starting from dummy->next
        return dummy->next;
    }
};
Enter fullscreen mode Exit fullscreen mode

Odd Even Linked List

This question is part of Leetcode problems, question no. 328.

Here’s the Solution class for the "Odd Even Linked List" problem in C++:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) return nullptr;

        // Initialize pointers for odd and even nodes
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even; // Keep track of the start of even list

        // Iterate through the list to rearrange the nodes
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next; // Link the odd nodes
            odd = odd->next;        // Move to the next odd node
            even->next = odd->next; // Link the even nodes
            even = even->next;      // Move to the next even node
        }

        // Attach the even list at the end of the odd list
        odd->next = evenHead;

        return head;
    }
};
Enter fullscreen mode Exit fullscreen mode

Palindrome Linked List

This question is part of Leetcode problems, question no. 234.

Here’s the Solution class for the "Palindrome Linked List" problem in C++:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;

        // Step 1: Find the middle of the linked list using the fast and slow pointer technique
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half of the list
        ListNode* prev = nullptr;
        while (slow) {
            ListNode* nextNode = slow->next;
            slow->next = prev;
            prev = slow;
            slow = nextNode;
        }

        // Step 3: Compare the first half and the reversed second half
        ListNode* firstHalf = head;
        ListNode* secondHalf = prev;

        while (secondHalf) {
            if (firstHalf->val != secondHalf->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }

        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Middle of the Linked List

This question is part of Leetcode problems, question no. 876.

Here’s the Solution class for the "Middle of the Linked List" problem in C++:

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // Move slow by one step and fast by two steps
        // When fast reaches the end, slow will be at the middle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};
Enter fullscreen mode Exit fullscreen mode
Image
15 Up-And-Coming Wall Mounted Electric Fireplace Bloggers You Need To See
Image
Wanneer is een echtscheiding officieel?
Image
Balancing AWS Certification and Parenting: A Guide for Busy Professionals

aws, certification, learning, cloud
Image
AppleTv

codepen
Image
Dampak dan Masalah Judi Online
Image
Five Tools That Everyone In The Gas Engineers Near Me Industry Should Be Making Use Of
Image
11 Ways To Completely Sabotage Your All Terrain Self Propelled Wheelchair Uk
Image
Hacking your first OAuth on the Web application

cybersecurity, security, writing
Image
The Ultimate Glossary Of Terms About Wall Mount For Electric Fireplace
Image
Langkah Manfaatkan Bonus Di Dalam Permainan Judi Online
Image
Maximize Your Wins at Plus Casino: Essential Strategies and Insights
Image
Deep Space Exploration Analytics: The Future of Data-Driven Space Exploration
Image
caluanie muelear oxidize price

beginners, programming, react, productivity
Image
How To Find The Perfect Corner Fabric Sofas On The Internet
Image
The Best Keyboards of 2024: Top Picks for Every Need and Budget

keyboards
Image
ketaksamaan slots online dengan off-line?
Image
Cream Fabric Corner Sofa: What's The Only Thing Nobody Is Discussing
Image
Five Things Everyone Makes Up About Asbestosis Compensation
Image
Design patterns using GO

programming, tutorial, systemdesign
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .