DEV Community

Cover image for Linked List Manipulation, Coding Interview Pattern
Harsh Mishra
Harsh Mishra

Posted on

Linked List Manipulation, Coding Interview Pattern

#interview #coding #algorithms #dsa

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

Top comments (0)

Read next

vjygour profile image

Understanding the Difference Between package.json and package-lock.json

Vijay Kumar -

mrcaption49 profile image

Finding the second highest salary in Oracle SQL

Pranav Bakare -

aqsagull99 profile image

Exploring Next.js 15: The Future of React 19 Applications

Aqsa Gull -

truongpx396 profile image

📝 30 Common PostgreSQL Interview Questions 🐘

Truong Phung -