Back-To-CP: day 2

14-10-2022

Delete the Middle Node of a Linked List

The problem is pretty straightforward. With the given head of a singly linked list, we delete the middle node. The definition of is given as middle = n/2 where n is the length of the list.
Since it's a singly linked list, traversal to black is not possible. So, it's necessary to get to the previous node of middle node or middle - 1.
Since only head is given, a traversal is needed to count the length. Then break the connection.

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if(head->next == nullptr){
            return nullptr;
        }
        int count = 0;
        ListNode* ptr = head;
        ListNode* ptr2 = head;

        while(ptr != nullptr){
            count++;
            ptr = ptr->next;
        }
        for(int i = 0; i < (count / 2) - 1; i++){
            ptr2 = ptr2->next;
        }

        ptr2->next = ptr2->next->next;
        return head;
    }
};

After accepted I looked for other efficient ways to solve this problem and learnt this new way called Slow pointer Fast pointer
This is a pretty straight forward technic to find middle of a list with unknown size. There is a slow pointer and fast pointer who starts from the beginning. The fast node increments itself twice more than the slow node. As a result, when the fast node already reaches the end, the slow pointer will be at the middle.

With first attempt I ran to an error
runtime error: member access within null pointer of type 'ListNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
for
while(f != nullptr || f->next != nullptr){
f = f->next->next;
s = s->next;
}
Turns out if I need to check both for pointer to be not null.

On the second attempt I got the same error. Because I initialize fast pointer before and if it was a list with length one, it gives us the error for accessing fast->next->next which doesn't exist.
So, an edge case was necessary.

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {

        if(head->next == nullptr){
            return 0;
        }

        ListNode *s = head;
        ListNode *f = head->next->next;

        while(f != nullptr && f->next != nullptr){
            f = f->next->next;
            s = s->next;
        }

        s->next = s->next->next;
        return head;
        return head;
    }
};

Reverse String

My approach was simple. Have two pointers at beginning and end. Swap the two pointer and increment and decrement the pointers accordingly.

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, h = s.size() - 1;
        while(l < h){
            swap(s[l], s[h]);
            l++;
            h--;
        }
    }
};