Remove zero Sum Consecutive Nodes from Linked List - How does this code works for test cases like this?

user_11973720 0
Viewed 357

I have a linked list like this as my input (1) -> (2) -> (3) -> (-3) -> (4) -> NULL
And I wish to remove the consecutive nodes which have sum equal to zero i.e., I want my output linked list to be like this: (1) -> (2) -> (4) -> NULL

I have already solved this problem using approach of map and array, and then I came across the code shown below. And this code works perfectly fine for the the above test case and I'm unable to understand how?

/**
 * 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* removeZeroSumSublists(ListNode* head) {
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* cur = new_head;
        while(cur != NULL)
        {
            int sum=0;
            while(head != NULL)
            {
                sum += head->val;
                if(sum == 0)
                {
                   cur->next = head->next; 
                }
                head = head->next;
            }
            //What is happening here???
            cur = cur->next;
            if(cur != NULL)
            {
                head = cur->next;
            }
        }
        return new_head->next; 
    }
};

Could someone please provide me with an explanation?
data-structures linked-list c++
2 Answers

(cur) iterates from the beginning of the list. for every (cur) start summing the elements after (cur). when the sum=0 update (cur)->next to point to the first element after this sum. So the first K elements after (cur) with sum=0 are skipped.

This is done in loop until end of list. In every loop iteration the first K elements with sum=0 are skipped.

// the first K elements starting after (cur) with sum=0 are skipped,
//so (cur) now points to K+1.th element.
            cur = cur->next;
            if(cur != NULL)
            {
                head = cur->next;
            }

Time complexity is O(N*N).

user_12017010

The while loop sums values in consecutive nodes, and also creates a temporary node cur.

cur jumps two places in the list if the sum of current consecutive nodes is 0. At the end of each loop cycle, the traversing pointer in the list, named head, gets assigned the value of cur. This way, any pair of consecutive nodes with opposite values gets skipped, and thus not recorded in the list.

user_109475720
Related