2. Add Two Numbers (Java, LinkedList, Leetcode)

역순으로 되어있는 자리수마다 나뉘어져 있는 링크드리스트의 노드를 하나씩 순회하며 값을 더하고 그 결과를 반환하는 문제이다.

 

 

 

 

 

풀이

class Node {
    int val;
    Node next;
    Node (int val, Node next) {
        this.val = val;
        this.next = next;
    }
    Node (int val) {
        this.val = val;
    }
}

public class Problem {

    public Node makeListNode(int[] arr) {
        Node pointer, dummy = new Node(0);
        pointer = dummy;
        for (var i : arr) {
            pointer.next = new Node(i);
            pointer = pointer.next;
        }
        return dummy.next;
    }

    public Node sumOfTwoLinkedList(Node n1, Node n2) {
        var carry = 0;
        Node pointer, dummy = new Node(0);
        pointer = dummy;
        while (n1 != null || n2 != null || carry != 0) {
            if (n1 != null) {
                carry += n1.val;
                n1 = n1.next;
            }
            if (n2 != null) {
                carry += n2.val;
                n2 = n2.next;
            }

            pointer.next = new Node(carry % 10);
            carry /= 10;
            pointer = pointer.next;
        }
        return dummy.next;
    }
}

 

출력

public static void main(String[] args) {
    Problem problem = new Problem();

    var arr1 = new int[] {2,4,3};
    var arr2 = new int[] {5,6,4};

    var node1 = problem.makeListNode(arr1);
    var node2 = problem.makeListNode(arr2);

    var result = problem.sumOfTwoLinkedList(node1, node2);
    while (result != null) {
        System.out.println(result.val); // 7 0 8
        result = result.next;
    }
}

 

핵심 아이디어

해당 문제 풀이의 핵심은 dummy로 임의의 Node를 하나 생성하고 pointer를 dummy로부터 값을 추가해나가는 방식이다.

dummy를 생성하고 그 값을 저장해두는 이유는 순회의 시작지점인 head의 위치를 기억해놓기 위함이며 

pointer는 어떤 값을 가지는 Node가 아닌 Node간의 연결만을 담당하는 값이다.

 

그래서 다음과 같이 pointer.next에 새로운 Node를 생성해서 값을 넣어주고 pointer를 그 다음 pointer로 이동하는 것이 가능하다.

pointer.next = new Node(carry % 10);
pointer = pointer.next;

 

Node의 val은 자리수를 의미하므로 한쪽 Node가 null이 되더라도 값을 문제없이 이어나갈 수 있다.

carry는 올려야되는 값이 있는지 여부를 나타내는 값이므로 가장 마지막 Node끼리 더해서 10 이상인 경우 마지막에 1을 나타내는 새로운 Node를 생성해야 하기에 해당 조건에 대해서도 체크해야 한다.

while (n1 != null || n2 != null || carry != 0)

 

레퍼런스

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode