C언어 ] leetCode 2181 - Merge Nodes in Between Zeros

 

 

 

 

You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.

Return the head of the modified linked list.

 

Example 1:

 

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

 

Example 2:

 

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

 

Constraints:

• The number of nodes in the list is in the range [3, 2 * 105].
• 0 <= Node.val <= 1000
• There are no two consecutive nodes with Node.val == 0.
• The beginning and end of the linked list have Node.val == 0.

 

 

 

 

 

 

val이 0이 아닐 땐 sum에 accumulate하며 prev->next = current = current->next; 로 current node를 삭제한 뒤 다음 노드로 넘어가고,

val이 0일 때는 sum을 val에 대입한 뒤 초기화하고, prev = current; current = current->next;로 노드를 계속 순회한다.

순회 끝나면 맨 앞의 0 제외하고 head->next 리턴하고 끝

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeNodes(struct ListNode* head){
    int sum = 0;

    struct ListNode *prev = head;
    struct ListNode *current = head->next;

    while(current != NULL)
    {
        if(current->val != 0)
        {
            sum += current->val;
            prev->next = current = current->next;
        }
        else
        {
            current->val = sum;
            sum = 0;
            prev = current;
            current = current->next;
        }
    }

    return head->next;
}