LeetCode 2181. Merge Nodes in Linked List 자바 문제 풀이

문제 설명

• 문제: https://leetcode.com/problems/merge-nodes-in-between-zeros/
• 설명: 주어진 단일 연결 리스트에서 특정 조건에 따라 노드를 합치는 작업을 수행해야 합니다.

접근 방식

• 아이디어:
  • 링크드리스트를 순회하면서 값이 0인지 확인합니다.
  • 값이 0이 아니면 더해서 저장해둡니다.
  • 값이 0인 노드를 찾으면, 지금까지 더한값을 가진 새로운 노드를 생성하고, 새로운 링크드리스트에 추가합니다.
• 알고리즘:
  1. 값이 0인 노드를 넣어둘 링크드리스트 resultNode를 생성합니다.
  2. 나중에 리턴하기위해 더미헤드를 생성하여 resultNode에 연결해놓습니다.
  3. 더한 값을 넣어둘 변수 addedVal을 생성합니다.
  4. 주어진 링크드리스트를 순회합니다.
  5. 노드의 값이 0이 아닌경우 값을 더합니다.
  6. 노드의 값이 0인 경우 지금까지 더한 값을 가진 새로운 노드를 생성하고, 이를 새로운 링크드리스트인 resultNode에 추가합니다.
  7. 더한 값을 넣어둔 변수 addedVal을 초기화 합니다.
  8. 더미헤드.next를 리턴합니다.

코드

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;
    }
}

결론

• 시간 복잡도: 연결 리스트를 한 번 순회하는 O(n)의 시간 복잡도가 필요합니다.
• 공간 복잡도: 추가적인 공간을 거의 사용하지 않으므로 O(1)입니다.