2nd Week - Algorithms

5. Merge Two Sorted Lists (Easy)

🔗 Problem Link

🧱 Context:

• Written in C++.
• Merges two sorted singly linked lists into a new sorted list.
• A singly linked list is a structure where each node holds a value (val) and a pointer to the next node (next).

---

🧩 ListNode Structure

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

• val: value of the node
• next: pointer to the next node

Three constructors:

1. Default: val = 0, next = nullptr
2. With value only
3. With value and next node pointer

---

🧠 Solution Class

class Solution {
public:

• Class for our solution
• public: means the method is accessible externally

---

🔧 mergeTwoLists Method

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

• Takes two pointers to sorted lists
• Returns pointer to a new merged sorted list

---

🧱 Step 1: Create dummy starting node

ListNode* dummyHead = new ListNode();

Used as a fake starting point to simplify appending new nodes.

---

📍 Step 2: Create traversal pointer

ListNode* current = dummyHead;

current moves along the new list.

---

🔄 Step 3: While both lists aren't finished

while (list1 && list2) {

Continue while both lists have nodes.

---

🔁 Step 4: Compare values

if (list1->val <= list2->val) {

Choose the smaller value.

---

➡️ Step 5: Append from list1

current->next = list1;
list1 = list1->next;

---

🔁 Otherwise, take from list2

} else {
    current->next = list2;
    list2 = list2->next;
}

---

🧭 Step 6: Move forward in the new list

current = current->next;

---

🔚 Step 7: Attach remaining nodes

current->next = list1 ? list1 : list2;

---

🏁 Step 8: Return the merged list

return dummyHead->next;

Return the first real node (skip dummy).

---

✅ Summary:

1. Create a dummy node
2. Traverse both lists
3. Choose the smaller node each time
4. Attach the rest when one list ends
5. Return merged result

---

6. Reverse Linked List (Easy)

🔗 Problem Link

---

🔹 ListNode Structure

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

---

🌀 reverseList Function

ListNode* reverseList(ListNode* head) {

• Input: pointer to start of the list
• Output: pointer to start of reversed list

---

Steps:

1. Create dummy head

ListNode* dummy = new ListNode();

1. Pointer for traversal

ListNode* current = head;

1. Loop through list

while (current != nullptr) {

1. Save the next node

ListNode* nextNode = current->next;

1. Reverse pointer

current->next = dummy->next;

1. Insert at start of new list

dummy->next = current;

1. Move to next

current = nextNode;

1. Return reversed list

return dummy->next;

---

🧩 Visual Walkthrough

Original:

head → 1 → 2 → 3 → 4 → nullptr

After iterations:

dummy → 1
dummy → 2 → 1
dummy → 3 → 2 → 1
dummy → 4 → 3 → 2 → 1

---

🟡 Recap:

1. Create empty list
2. Take nodes one by one from original
3. Insert at beginning of new list
4. Return result

---

7. Linked List Cycle (Easy)

🔗 Problem Link

---

📦 Node Structure

struct ListNode {
    int value;
    ListNode *next;
    ListNode(int x) : value(x), next(nullptr) {}
};

---

🧠 Cycle Detection (hasCycle)

bool hasCycle(ListNode *head) {

---

🐢🐇 Use two pointers:

ListNode *slowPointer = head;
ListNode *fastPointer = head;

• slowPointer moves 1 step
• fastPointer moves 2 steps

---

🔁 Traverse the list

while (fastPointer && fastPointer->next) {
    slowPointer = slowPointer->next;
    fastPointer = fastPointer->next->next;

If they meet:

if (slowPointer == fastPointer)
    return true;

No cycle?

return false;

---

📊 Visual

Without cycle:

1 → 2 → 3 → 4 → nullptr

With cycle:

1 → 2 → 3 → 4
          ↑
          ↓
          2 (loop)

---

🧩 Summary:

• Two pointers moving at different speeds
• If cycle exists → they'll meet
• If not → fast pointer hits end

---

8. Maximum Subarray (Medium)

🔗 Problem Link

---

📦 The Problem:

Given an array, find the maximum sum of any continuous subarray.

Example:
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 → from [4, -1, 2, 1]

---

🧠 Kadane’s Algorithm

int maxSubArray(vector<int>& nums) {

---

🔹 Step 1: Initialize max values

int currentMax = nums[0];
int globalMax = nums[0];

---

🔁 Step 2: Iterate

for (int i = 1; i < nums.size(); ++i) {
    currentMax = std::max(currentMax, 0) + nums[i];
    globalMax = std::max(globalMax, currentMax);
}

---

✅ Step 3: Return result

return globalMax;

---

🧩 Example Breakdown

i	nums[i]	currentMax	globalMax
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6 ✅	6
7	-5	1	6
8	4	5	6

---

🟡 Summary:

• currentMax: sum of current subarray
• Reset to 0 if it turns negative
• globalMax: max seen so far
• One pass: O(n) complexity

---

✅ Follow-up

If you liked this breakdown, let me know — I plan to continue this series with more Leetcode problems, especially in C++ with deep explanations for beginners.

---