[기술 면접 코딩 인터뷰 준비] 연결 리스트 - 두 숫자 더하기 알고리즘(Add Two Numbers)

제가 면접에서 carry 를 빠뜨렸던 순간

작년에 기술 면접에서 Add Two Numbers 를 처음 마주했을 때, 저는 문제를 보자마자 “각 노드의 값을 더하고 10 이 넘으면 다음 자리로 넘긴다”라는 흐름이 그대로 떠올라 별로 겁이 나지 않았습니다. 그래서 while 문으로 두 리스트를 끝까지 따라가며 digit 합을 만들고, carry 가 생기면 다음 자리로 넘기는 구현을 5 분도 되지 않아 작성했었습니다. 코드는 분명히 그 자리에서 잘 돌아가는 것처럼 보였고, 마지막 입출력 한 케이스에서도 답이 나와서 저는 그대로 제출했었습니다.

면접관께서 “l1=[9,9], l2=[1] 케이스도 한 번 돌려 보시겠어요?”라고 물으셨을 때, 결과는 0,0 이 아니라 0,0 다음에 1 이 따라와야 한다는 사실을 제가 빠뜨렸다는 점이 드러났습니다. while 문을 빠져나온 다음에 carry 가 남아 있을 수 있다는 사실. 그 한 줄을 제가 놓쳤던 것입니다. 면접은 그 자리에서 끝났지만, 저는 그 짧은 입출력 한 케이스 때문에 “정답 처럼 보이는 오답”을 짜 둔 셈이었다는 교훈을 오래 안고 갔습니다. 이후로 저는 알고리즘 문제 앞에서 “마지막 carry 처리했는가?”라는 한 줄을 코드 안에 박아 두는 습관을 갖게 되었습니다.

LeetCode 토론방과 Reddit r/cscareerquestions를 살펴보면 이 문제에서 반복되는 실수 패턴이 세 가지로 압축됩니다. 첫째, while 조건을 (l1 != null && l2 != null) 로 잡아서 한쪽 리스트가 끝나는 순간 나머지를 날려버리는 실수입니다. 반드시 || 를 써야 짧은 쪽이 끝난 뒤에도 긴 쪽을 계속 처리할 수 있습니다. 둘째, 입력 리스트를 직접 수정하는 실수입니다. l1.val = sum % 10 처럼 원본 노드를 덮어쓰면 같은 리스트가 다른 곳에서 재사용될 때 예상치 못한 버그가 납니다. 셋째, 마지막 carry 를 빠뜨리는 실수인데, 이것이 제가 면접에서 직접 당한 바로 그 함정입니다. l1=[9,9,9], l2=[1] 입력에서 결과는 [0,0,0,1] 이어야 하지만 carry 처리가 없으면 [0,0,0] 에서 잘려버립니다.

역순으로 저장된 두 연결 리스트를 더하는 흐름 자체는 아래 그림처럼 단순합니다. 한 자리씩 더하고, 합이 10 을 넘으면 carry 를 다음 자리로 넘기며, 두 리스트 중 짧은 쪽은 0 으로 채워서 끝까지 진행합니다.

제가 처음 짰던 오답 코드: carry 가 밖으로 새는 경우

첫 시도에서 저는 while 문 안에서만 carry 를 다루고, 루프가 끝나는 자리에 별도 처리를 두지 않았습니다. 그 결과는 짧은 입력에서는 우연히 맞아 보이지만, 마지막 자리에서 carry 가 살아남는 입력에서는 동 떨어진 노드 한 개를 잃어 버립니다. 면접관은 보통 “이 케이스에서 출력이 어떻게 되나요?”라고 질문해 같은 함정을 짚어 보실 때가 많습니다.

// Before: while 문을 빠지고 나면 carry 가 묻혀 버리는 첫 시도
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0); // 더미 머리
    ListNode cur = result;             // 다음 노드를 붙일 위치
    int carry = 0;
    while (l1 != null || l2 != null) {
        int v1 = l1 != null ? l1.val : 0; // 끝난 쪽은 0 으로 채웁니다
        int v2 = l2 != null ? l2.val : 0; // 끝난 쪽은 0 으로 채웁니다
        int sum = v1 + v2 + carry;        // 자릿수와 받은 carry 를 합칩니다
        carry = sum >= 10 ? 1 : 0;        // 다음 자리 carry 를 갱신합니다
        cur.next = new ListNode(sum % 10);// 현재 자리 결과를 새 노드로 만듭니다
        cur = cur.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    // ⚠️ 여기서 carry 가 남아 있는데 별도 처리가 없습니다
    return result.next;
}

이 코드는 “마지막 l1 l2 가 둘 다 끝났을 때 carry 가 1 일 수 있다”는 가능성을 그냥 묻어 두기 때문에 오답이 됩니다. 면접에서 가장 빠르게 받는 지적이 바로 이 자리이므로, 코드를 제출하기 전에 “루프 후에 carry 검사를 한 번 더 했는가?”라고 자문해 보시면 같은 함정을 피하실 수 있습니다.

또한 while 조건이 && 가 아닌 || 여야 한다는 점도 주목하십시오. && 로 잡으면 한쪽이 null 이 되는 순간 루프를 빠져나오기 때문에, 길이가 다른 두 리스트에서 반드시 오답이 납니다. 커뮤니티 토론에서 “맞는 것 같은데 왜 틀렸나요?”라는 질문의 절반 이상이 바로 이 && 실수에서 비롯됩니다.

제가 지금 쓰는 정답 코드: while 종료 후 carry 점검 + 더미 머리

오답을 짚고 나면 정답 코드는 자연스럽게 따라옵니다. 핵심은 두 가지입니다. 첫째, “마지막 루프가 끝났을 때 carry 가 남아 있다면 자릿수 하나를 더 만든다”. 둘째, “더미 머리 노드를 두어 첫 노드 삽입을 일반화한다”. 저는 이 두 가지가 한 줄짜리 변경이지만 익숙해지면 면접에서 자주 받는 후속 질문까지 단단하게 받아낼 수 있다는 점을 그 자리에서 배웠습니다.

// After: while 종료 후의 carry 까지 책임지는 정답 코드
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0); // 더미 머리입니다. 첫 노드 삽입을 일반화합니다
    ListNode cur = result;
    int carry = 0;
    while (l1 != null || l2 != null) {
        int v1 = l1 != null ? l1.val : 0; // 짧은 쪽은 0 으로 채웁니다
        int v2 = l2 != null ? l2.val : 0; // 짧은 쪽은 0 으로 채웁니다
        int sum = v1 + v2 + carry;        // 자릿수와 carry 를 합칩니다
        carry = sum >= 10 ? 1 : 0;        // 다음 자리 carry 를 갱신합니다
        cur.next = new ListNode(sum % 10);// 현재 자리 결과를 새 노드로 만듭니다
        cur = cur.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    if (carry != 0) {                     // while 종료 직후 carry 가 남아 있다면 자릿수를 하나 더 만듭니다
        cur.next = new ListNode(carry);
    }
    return result.next;                   // 더미 머리 다음이 실제 결과의 출발점입니다
}

더미 머리 노드를 두면 “첫 노드가 없을 때”라는 케이스 분기가 사라져 코드가 한결 단순해집니다. 그리고 마지막 if (carry != 0) 분기 한 줄. 이 한 줄이 면접을 가르는 결정적 차이라는 것을 제가 직접 겪으면서 절실히 배웠습니다. 면접관 입장에서는 “carry 가 살아남는 케이스를 미리 짚었는가”가 곧 “운영 사고를 한 번이라도 다뤄 본 사람인가”라는 신호로 읽히게 됩니다.

면접관이 자주 받는 후속 질문 두 가지

이 문제를 무난하게 풀어 내셨다면, 면접에서는 보통 두 가지 후속 질문을 받으실 가능성이 큽니다. 첫 번째는 “리스트의 길이가 다르면 어떻게 합니까?”이고, 두 번째는 “자릿수가 역순이 아니라 정순이라면 어떻게 푸시겠습니까?” 입니다. 두 질문 다 짧은 대답이 가능하지만, 저는 그 자리에서 한 줄을 더 곁들이면 신뢰도가 많이 올라간다는 점을 배웠습니다.

첫 번째 질문인 길이가 다른 두 리스트에 대해서는 위 코드처럼 “끝난 쪽은 0 으로 채운다”는 한 줄 트릭을 짚어 주시면 충분합니다. 두 리스트가 끝나는 시점이 달라도 while 의 || 조건과 더미 값을 활용해 어떤 자리도 빠뜨리지 않고 더할 수 있습니다. 면접관은 이어서 “null 처리는 어떻게 하셨나요?”라고 물으실 수 있는데, 그때도 “각 자리 접근 전에 null 검사를 두어 0 으로 치환했습니다”라는 한 줄이면 충분합니다.

두 번째 질문인 정순 입력에 대해서는 저는 두 가지 길을 미리 정리해 둡니다. 첫 번째는 “스택에 두 리스트를 모두 담은 뒤 스택에서 꺼내며 더하기” 하는 방법이고, 두 번째는 “리스트를 뒤집은 뒤 같은 알고리즘으로 더하고, 결과를 다시 뒤집기” 입니다. 정답 자체는 둘 중 어느 쪽이어도 큰 차이가 없지만, “메모리 면에서 스택은 O(max(m, n)) 을 추가로 쓰고, 뒤집기는 in-place 에 가깝습니다”라는 비교 한 줄을 곁들이면 면접관 입장에서 “복잡도까지 따져 본 사람”이라는 인상을 받게 됩니다.

제가 추천드리는 시험 케이스 4 가지

Add Two Numbers 는 짧은 코드를 짜면서도 함정이 많은 문제라, 저는 항상 다음 4 가지 입력을 머릿속에서 한 번씩 돌려 봅니다. 면접에서 “한 번 마지막에 한 번 더 실행해 보시겠어요?”라고 권해 주시는 분이 있다면, 이 4 가지를 미리 짚어 두셨다는 이야기이므로 한 번씩 답변해 보시면 자연스럽게 차이를 보여 드릴 수 있습니다.

• 입력 [0, 1] + [0, 1, 2], 한쪽 리스트가 다른 쪽보다 짧습니다. 더미 0 으로 채우는 트릭 없이 풀 수 없습니다.
• 입력 [] + [0, 1], 한쪽이 빈 리스트입니다. null 가드를 두지 않으면 NullPointerException 으로 죽는 자리입니다.
• 입력 [9, 9] + [1], 마지막 자리에서 carry 가 살아남습니다. 제가 면접에서 진짜로 짚었던 자리이기도 합니다.
• 입력 [0] + [0], 두 리스트 모두 “0” 하나만 있는 가장 작은 경우입니다. 더미 머리를 두면 답이 노드 한 개 (값 0) 로 나오는지가 검증됩니다.

저는 이 네 가지 입력을 순서대로 짚으며 “이 케이스에서 출력은 무엇이 되나요?”라고 말하는 습관을 갖고 있는데, 면접관 입장에서는 짧은 시간 안에 코너 케이스를 짚는 사람이라는 인상을 받으시게 됩니다. 사실 입력이 짧아서 손으로 직접 노드를 그려 보셔도 1 분 안에 확인이 되니, 시간을 거의 안 쓰면서도 검증 신뢰도를 크게 올릴 수 있는 방법입니다.

복잡도 정리와 마지막으로 한 줄

위 코드의 시간 복잡도는 while 문이 두 리스트 중 긴 쪽 만큼만 돕니다. 따라서 O(max(m, n)) 입니다. 공간 복잡도도 새 결과 리스트에 노드를 두 리스트 중 긴 쪽 만큼 만들기 때문에 같은 O(max(m, n)) 입니다. m 과 n 은 각각 l1 과 l2 의 길이를 의미합니다. 정순 변형(Add Two Numbers II) 의 경우 같은 복잡도를 유지하면서 스택을 쓰면 O(max(m, n)) 의 추가 메모리가 따라오고, 뒤집기를 쓰면 O(1) 의 추가 메모리로 끝납니다.

마지막으로 한 줄만 적어 두겠습니다. Add Two Numbers 는 “답이 맞는지 확인하기 위해” 짜는 문제가 아니라, “마지막 자리에 carry 가 남아 있는 케이스까지 책임지고 끝내는가”가 시험되는 문제입니다. 더미 머리를 두고, while 을 (l1 != null || l2 != null) 로 잡고, 루프 종료 후 carry 를 한 번 더 점검하는 이 세 가지가 한 자리에 모이면, 짧은 분량 안에서도 운영 사고를 한 번쯤 다뤄 본 사람이라는 신뢰를 면접관에게 받으실 수 있습니다. 작은 문제이지만 면접관은 이 작은 문제에서 그런 신호를 읽으려 하신다는 점을 한 번 기억해 두시면 좋겠습니다.