LeetCode 2181. Merge Nodes in Linked List Java Solution

Problem Description

• Problem: https://leetcode.com/problems/merge-nodes-in-between-zeros/

• Description: Given a single linked list, the task is to merge nodes according to specific conditions. Add node's values until it reaches 0.

• 0-3-4-0-5-3-0 to 7-8

Approach

• Idea:

  • Traverse the linked list while checking if the value is 0.

  • If the value is not 0, add it to a cumulative sum.

  • When encountering a node with a value of 0, create a new node with the cumulative sum and add it to a new linked list.

• Algorithm:

  1. Create a new linked list resultNode to store nodes with a value of 0.

  2. Create a dummy head node and connect it to resultNode for later return.

  3. Create a variable addedVal to store the cumulative sum.

  4. Traverse the given linked list.

  5. If the node's value is not 0, add the value to addedVal.

  6. If the node's value is 0, create a new node with the cumulative sum and add it to the new linked list resultNode.

  7. Reset the addedVal variable.

  8. Return dummyHead.next.

Code

class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode temp = head.next;
        ListNode dummyHead = new ListNode();
        ListNode resultNode = dummyHead;
        int addedVal = 0;

        while(temp != null) {
            addedVal += temp.val;

            if(temp.val == 0) {
                resultNode.next = new ListNode(addedVal);
                resultNode = resultNode.next;
                addedVal = 0;
            }

            temp = temp.next;
        }

        return dummyHead.next;
    }
}

Conclusion

• Time Complexity: The algorithm requires O(n) time complexity since it traverses the linked list once.

• Space Complexity: The algorithm uses constant extra space, so the space complexity is O(1).