문제 개요
숫자(digit)들로 구성된 비어 있지 않은 단일 연결 리스트(singly linked list)가 하나의 음이 아닌 정수를 나타낸다고 가정해 봅시다. 우리가 해야 할 일은 이 정수에 1을 더하는 것입니다. 단, 0 자체를 제외하면 정수 앞에 붙는 불필요한 0(선행 제로)은 없으며, 연결 리스트에서 최상위 자릿수는 리스트의 머리(head)에 위치한다고 가정합니다.
예를 들어 입력이 [1, 2, 3]이라면 1을 더한 결과인 [1, 2, 4]를 출력해야 합니다.
접근 방법
이 문제의 핵심 아이디어는 간단합니다. 덧셈에서 올림(carry)이 발생하는 경우는 끝자리부터 연속된 9가 나타날 때뿐입니다. 따라서 값이 9가 아닌 마지막 노드를 찾아 그 값을 1 증가시키고, 그 뒤에 있는 모든 9를 0으로 바꾸면 됩니다. 만약 리스트 전체가 9로만 이루어져 있다면, 맨 앞에 값이 1인 새 노드를 추가하고 기존 노드들을 모두 0으로 만들면 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
head가 null이면 head를 그대로 반환합니다.
curr = head, req = NULL로 초기화합니다.
curr이 null이 아닐 때까지 반복합니다.
curr의 값(val)이 9가 아니라면 req := curr로 갱신합니다.
curr := curr의 next로 이동합니다.
req가 여전히 NULL이라면(모든 자릿수가 9인 경우):
값이 1인 새 노드 dummy를 생성합니다.
dummy의 next를 head로 연결합니다.
head부터 끝까지 모든 노드의 값을 0으로 변경합니다.
dummy를 반환합니다.
그렇지 않다면:
req의 값을 1 증가시킵니다.
req := req의 next로 이동한 뒤, 남은 노드들을 모두 0으로 바꿉니다.
head를 반환합니다.
이 방식은 리스트를 한 번 또는 두 번 순회하므로 시간 복잡도는 O(n), 추가 공간은 상수 수준(O(1))으로 매우 효율적입니다.
구현 예제
이해를 돕기 위해 다음 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode *next;
ListNode(int data) {
val = data;
next = NULL;
}
};
ListNode* make_list(vector<int> v) {
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head) {
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head)
return head;
ListNode* curr = head;
ListNode* req = NULL;
while (curr) {
if (curr->val != 9) {
req = curr;
}
curr = curr->next;
}
if (!req) {
ListNode* dummy = new ListNode(1);
dummy->next = head;
while (head) {
head->val = 0;
head = head->next;
}
return dummy;
}
else {
req->val++;
req = req->next;
while (req) {
req->val = 0;
req = req->next;
}
return head;
}
}
};
int main() {
Solution ob;
vector<int> v = {1,4,5};
ListNode *head = make_list(v);
print_list(ob.plusOne(head));
}
입력
{1,4,5}출력
[1, 4, 6]
위 예제에서 입력 리스트는 145를 나타내며, 1을 더한 결과인 146이 [1, 4, 6] 형태로 출력됩니다. 만약 입력이 [9, 9, 9]였다면 모든 자릿수가 9이므로 새로운 헤드 노드 1이 추가되어 [1, 0, 0, 0]이 반환됩니다.