연결리스트로 표현되는 숫자에 1을 더함

숫자의 연결된 목록 표현은 다음과 같이 제공됩니다. 연결된 목록의 모든 노드는 숫자의 한 자리로 간주됩니다. 노드는 연결된 목록의 첫 번째 요소에 해당 숫자의 가장 중요한 숫자가 포함되고, 연결된 목록의 마지막 요소에 해당 숫자의 최하위 숫자가 포함되도록 숫자를 저장합니다. 예를 들어 숫자 202345는 연결된 목록에서 (2->0->2->3->4->5)로 표시됩니다.

숫자를 나타내는 이 연결 리스트에 1을 더하려면 리스트에서 최하위 비트의 값을 확인해야 합니다. 9보다 작으면 괜찮습니다. 그렇지 않으면 코드가 다음 숫자 등을 변경합니다.

이제 이를 수행하는 방법을 이해하기 위한 예를 살펴보겠습니다. 1999는 (1->9->9 ->9)로 표시되며 1을 추가하면 (2->0->0->0)으로 변경됩니다.

Input:1999
Output:2000

Explanation

주어진 연결 목록이 나타내는 숫자에 1을 더하세요. 이는 다음 단계를 따라야 함을 의미합니다.

• 연결 목록 반전: 연결 목록을 반전해야 합니다. 즉, 마지막을 변경해야 합니다. 첫 번째부터 번호, 첫 번째가 마지막이 됩니다. 예를 들어 1->9->9->9는 9->9->9->1로 변환됩니다.
• 이 역방향 연결 목록의 경우 연결 목록을 순회하여 가장 왼쪽 노드에 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;
}

위 내용은 연결리스트로 표현되는 숫자에 1을 더함의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!