[Leetcode]2181. Merge Nodes in Between Zeros

문제 요약

• 알고리즘 분류: LinkedList, 구현
• 난이도: Medium
• 문제내용:
  • 0 사이에 값을 합쳐서 하나의 노드로 표현해라.
• 사이트 주소:https://leetcode.com/problems/merge-nodes-in-between-zeros/description/

문제풀이

 이번 문제는 링크드리스트 노드 클래스나 구조체를 활용하는 문제이다. 노드클래스에 대한 이해도만 있으면 문제 푸는데는 어렵지 않다. 일단 아래그림처럼 처음에 나온 링크드 리스트에서 0사이 값을 합쳐서 다시 링크드리스트를 만들기만 된다.

 

그림을 보면 어떻게 구현 해야 할지 보일것이다. 그럼 구현은 아래처럼 하면된다.

1. 노드 새로 인스턴스 한다.
2. 다음노드가 끝있을때까지 반복문을 돌린다.
   1. 현재 노드가 0이 아니면 인스턴스한 노드에 값을 더하고 다음 노드로 이동한다.
   2. 현재 노드 0일때 새로 노드 인스턴스만들고 새로 만든 인스터스를 다음 노드로 지정하고 그 노드에 값을 추가하도록 한다.

이렇게 구현하면 시간복잡도는 노드개수 N개 라고 할때 O(N)만큼 나온다. 위 구현대로 한다고 해도 어떻게 구현 해야 할지 막막할수도 있다. 그래서 아래 코드를 참고하면서 보면 된다.

Code

Python

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nowNode = ListNode(0)
        nextNode = head.next
        resultNode = nowNode # 결과를 제출 하기 위해서 시작노드를 따로 지정한다.

        while(True):
            # 값이 0일때
            if(nextNode.val == 0):
                # 다음 노드 없을경우
                if(nextNode.next == None):
                    break
                # 다음노드 초기화한다.
                nowNode.next = ListNode(0)
                nowNode = nowNode.next
            else:
                # 현재 노드 값을 추가한다.
                nowNode.val += nextNode.val
            # 기존 노드 다음으로 이동한다.
            nextNode = nextNode.next

        return resultNode

Java

class Solution {
    public ListNode mergeNodes(ListNode head) {

        ListNode nowNode = new ListNode(0); 
        ListNode nextNode = head.next;
        ListNode resultNode = nowNode;// 결과를 제출 하기 위해서 시작노드를 따로 지정한다.

        while(true){
            // 값이 0일때
            if(nextNode.val == 0){
                // 다음 노드 없을경우
                if(nextNode.next == null){
                    break;
                }
                //다음노드 초기화한다.
                nowNode.next = new ListNode(0);
                nowNode = nowNode.next;
            }else{
                // 현재 노드 값을 추가한다.
                nowNode.val += nextNode.val;
            }
            // 기존 노드 다음으로 이동한다.
            nextNode = nextNode.next;
        }

        return resultNode;
    }
    
}