Problem Desc

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.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode() # 최종적으로 return할 ListNode
        prev = dummy # dummy의 포인터

        _sum = 0 # 합
        while head:
            if _sum and head.val == 0: # 현재 값이 0이라면
            	# prev.next를 이전에 계산한 합을 ListNode로 만들어서 설정한다.
                prev.next = ListNode(_sum) 
                _sum = 0 # 다음 합 계산을 위해 0으로 초기화
                prev = prev.next # 포인터 이동
            # 현재 값이 0이 아니라면
            else:
                _sum += head.val # 계속해서 합을 계산
                
            # head의 포인터 이동
            head = head.next 
        
        return dummy.next # dummy는 ListNode(0)으로 시작하므로 next를 return

Code Desc

내가 취약한 포인터에 관한 문제이다.
문제의 알고리즘은 다음과 같다.

(이때, 포인터로 사용하는 것은 head이다.)

1. 현재 포인터의 값이 0이 아니라면, 합을 계산한다.
2. 현재 포인터의 값이 0이라면, 이전에 계산한 합으로 새로운 ListNode를 설정한다.
   2.1 prev.next에 새로운 ListNode를 설정한다.
   2.2 다음 계산을 위해, 계산한 합을 0으로 설정한다.
   2.3 새로운 ListNode를 붙이기 위해, prev = prev.next로 설정한다.(포인터 이동)
3. 현재 포인터를 갱신한다( head = head.next )
4. 현재 포인터가 None이 아닐 때까지 위의 과정을 반복한다.

마지막으로 return dummy.next
(dummy.next를 return 하는 이유 : dummy는 0 - val1 - val2 - ... 이런 형태를 가지므로 )