leetcode 2. AddTwoNumbers (Java, 설명포함)

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

문제

숫자 하나를 역순으로 저장한 LinkedList가 2개 주어지고, 두 수를 더한 것을 역순으로 저장한 LinkedList로 반환하라.

풀이

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode l1CurrentNode = l1;
    ListNode l2CurrentNode = l2;

    boolean olim = false;
    Stack<Integer> answerStack = new Stack<>();
    while (l1CurrentNode != null || l2CurrentNode != null || olim) {
        int currentInteger = olim ? 1 : 0;
        if (l1CurrentNode != null) {
            currentInteger += l1CurrentNode.val;
            l1CurrentNode = l1CurrentNode.next;
        }
        if (l2CurrentNode != null) {
            currentInteger += l2CurrentNode.val;
            l2CurrentNode = l2CurrentNode.next;
        }
        if (currentInteger > 9) {
            olim = true;
            currentInteger -= 10;
        } else {
            olim = false;
        }
        System.out.println(currentInteger);
        answerStack.push(currentInteger);
    }

    ListNode answerNode = null;
    while (!answerStack.empty()) {
        ListNode currentNode = new ListNode(answerStack.pop(), answerNode);
        answerNode = currentNode;
    }

    return answerNode;
}
@Test
@DisplayName("q2AddtwoNumbers")
void test() {
    ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

    addTwoNumbers(l1, l2);
}

문제를 보자마자 Stack을 활용하면 될 것 같았습니다.
처음의 처음에는 Stack을 두 개 만들어서 각 LinkeList를 stack으로 저장하고 이상하게 풀어보다가
덧셈 연산을 바로바로 하면 될 것을 깨닫고, 오름차순으로 더하기를 진행하고 Stack에 쌓고, 올림은 따로 저장하고, 마지막에 Stack을 LinkedList로 변환했습니다. (while 문의 sout은 확인용으로, 성능에 악영향을 끼치니 확인 후 삭제하세요)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode headNode = new ListNode();
    ListNode currentNode = headNode;
    headNode.next = currentNode;

    boolean olim = false;
    while (l1 != null || l2 != null || olim) {
        int currentInteger = olim ? 1 : 0;
        if (l1 != null) {
            currentInteger += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            currentInteger += l2.val;
            l2 = l2.next;
        }
        if (currentInteger > 9) {
            olim = true;
            currentInteger -= 10;
        } else {
            olim = false;
        }

        currentNode.next = new ListNode(currentInteger);
        currentNode = currentNode.next;
    }

    return headNode.next;
}

leetcode의 예시 코드를 열심히 분석하여 수정한 코드입니다.

1. l1, l2는 그대로 사용해도 무방합니다. (매개변수 최대한 안건드리려는 버릇이...)
2. 별도로 Stack을 사용하지 말고 반환할 LinkedList를 Stack Queue형태로 저장할 방법을 생각해야 합니다.

ListNode headNode = new ListNode();
ListNode currentNode = headNode;
headNode.next = currentNode;

headNode의 값, 메모리주소를 'A 라고 할때, 이 부분에서 headNode = 'A, currentNode = 'A, headNode.next = 'A 입니다.

currentNode.next = new ListNode(currentInteger);
currentNode = currentNode.next;

 첫 번째 while문 내부 이 부분에서 정답 Node를 'B라고 할 때, 'A.next = 'B, currentNode = 'B 입니다. headNode는 호출된 적 없고 바뀌지 않아서 'A 그대로 가지고 있습니다. 
 두 번째 while 부터는 currentNode가 움직일 뿐입니다. 'A.next = 'B 입니다.

return headNode.next;

headNode인 'A는 큰 의미가 없습니다. 실제 정답인 'B를 반환해야합니다. headNode.next를 반환합니다.

---

LinkedList를 활용한 Stack 구현방법을 알아야합니다.
Queue 구현과 큰 차이 없으니, Queue와 같이 숙지해야겠습니다.

05.08 22:52 수정

해당 문제의 마지막에 사용된 자료구조는 stack이 아니라 queue입니다.
FIFO, 선입선출, 먼저 들어간 데이터가 먼저 나옵니다.
따라서, 일반적으로 Queue에서 사용하는 front, rear 로 node를 명명하고 front가 null 이냐에 따라

if (front == null) {
    this.front = new LinkedNode(value, null);
    this.rear = this.front;
} else {
    this.rear.next = new LinkedNode(value, null);
    this.rear = this.rear.next;
}

이렇게 작성하는게 더 직관적인 것 같습니다.