Merge Nodes In Between Zeros - Leetcode Solution

Problem Statement:

Given a singly linked list, you need to merge nodes of the list in-between nodes having a value of 0. In other words, if a linked list has 0 -> 1 -> 0 -> 2 -> 0 -> 3 -> 0 -> 4 nodes, you need to merge nodes 1 and 2, nodes 2 and 3, and nodes 3 and 4.

Function Signature:

ListNode* mergeBetweenZeros(ListNode* head);

Input:

The input contains a singly linked list.

Output:

The output is the linked list after merging nodes in-between nodes with a value of 0.

Approach:

To solve this problem, we can use a brute force method. We can iterate over the linked list and whenever we encounter a node with a value of 0, we can merge its adjacent nodes by changing pointers. We can use a temporary pointer to keep track of the previous node and merge the current node with the next node. We will continue this process until we reach the end of the linked list.

Algorithm:

1. Initialize a pointer to the head of the linked list and a boolean variable flag to false.
2. Traverse the linked list using a while loop until the end of the list is reached.
3. Check if the value of the current node is zero, if it is set the flag to true.
4. If the value of the current node is not zero but the flag is true, merge the current node with the previous node and set the flag to false.
5. Set the previous node pointer to the current node.
6. Move the current node pointer to the next node.
7. Return the head of the linked list.

Code:

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

ListNode* mergeBetweenZeros(ListNode* head) { ListNode *prev = NULL, *current = head; bool flag = false; while(current) { if(current->val == 0) { flag = true; } else { if(flag) { if(prev) { prev->next = current; } flag = false; } prev = current; } current = current->next; } if(flag && prev) { prev->next = NULL; } return head; }

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.

Space Complexity:

The space complexity of this algorithm is O(1), as we are not using any extra space to solve this problem.

Alternative Approach:

An alternative approach to solve this problem is to use recursion. We can recursively call the mergeBetweenZeros function on the next node until we reach the end of the linked list. Whenever we encounter a node with a value of 0, we can merge its adjacent nodes and return the merged node.

Code (using recursion):

ListNode* mergeBetweenZeros(ListNode* head) { ListNode *current = head; if(!head) { return head; } if(current->val == 0) { ListNode *temp = current; current = current->next; delete temp; return mergeBetweenZeros(current); } current->next = mergeBetweenZeros(current->next); return current; }

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.

Space Complexity:

The space complexity of this algorithm is O(n), as we are using the call stack for recursion and the space used by the call stack is proportional to the number of recursive calls.

1