숫자의 연결 목록 표현은 연결 목록의 모든 노드가 숫자의 한 자리 숫자로 처리되는 방식으로 제공됩니다. 노드는 연결 목록의 첫 번째 요소가 숫자의 최상위 숫자를 보유하고 연결 목록의 마지막 요소가 숫자의 최하위 비트를 보유하도록 숫자를 저장합니다. 예를 들어, 숫자 202345는 연결 목록에서 (2->0->2->3->4->5)로 표시됩니다.
그리고 이 연결 목록 표현 숫자에 1을 추가하려면 목록의 최하위 비트 값을 확인해야 합니다. 9보다 작으면 정상입니다. 그렇지 않으면 코드가 다음 숫자 등으로 변경됩니다.
이제 그것을 수행하는 방법을 알기 위해 예를 보겠습니다. 1999는 (1-> 9-> 9 -> 9)로 표시되며 여기에 1을 추가하면 (2->0->0->0)
Input:1999 Output:2000
설명
다음과 같은 몇 가지 단계를 수행하는 것을 의미하는 연결 목록으로 표시된 주어진 숫자에 1을 추가하려면,
- 연결 목록 반전:연결 목록을 반대로 해야 합니다. 즉, 마지막 숫자를 첫 번째 숫자로, 첫 번째 숫자를 마지막 숫자로 변경하는 것을 의미합니다. 예를 들어, 1-> 9-> 9 -> 9는 9-> 9 -> 9 ->1로 변환됩니다.
- 이 변경된 연결 목록에 대해 이제 목록을 탐색하고 가장 왼쪽 노드에 하나를 추가합니다. 이 노드의 값이 9와 같으면 다음 노드로 캐리를 전파합니다. 캐리가 올 때까지 동일한 절차를 수행합니다.
- 문자열을 원래 형식으로 되돌린 다음 헤드를 반환하여 문자열을 인쇄합니다.
예시
#include <iostream>
using namespace std;
//n=next node ; d=data ; p= previous node; h=head node; c=current node
class Node {
public:
int d;
Node* n;
};
Node *newNode(int d) {
Node *new_node = new Node;
new_node->d = d;
new_node->n = NULL;
return new_node;
}
Node *reverse(Node *h) {
Node * p = NULL;
Node * c = h;
Node * n;
while (c != NULL) {
n = c->n;
c->n = p;
p = c;
c = n;
}
return p;
}
Node *addOneUtil(Node *h) {
Node* res = h;
Node *temp, *p = NULL;
int carry = 1, sum;
while (h != NULL) {
sum = carry + h->d;
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
h->d = sum;
temp = h;
h = h->n;
}
if (carry > 0)
temp->n = newNode(carry);
return res;
}
Node* addOne(Node *h) {
h = reverse(h);
h = addOneUtil(h);
return reverse(h);
}
int main() {
Node *h = newNode(1);
h->n = newNode(9);
h->n->n = newNode(9);
h->n->n->n = newNode(9);
h = addOne(h);
while (h != NULL) {
cout << h->d;
h = h->n;
}
cout<<endl;
return 0;
}