Plus một danh sách được liên kết trong C ++

Giả sử chúng ta có một số nguyên không âm được biểu diễn dưới dạng không rỗng, một danh sách các chữ số được liên kết đơn lẻ, bây giờ chúng ta phải cộng một với số nguyên. Chúng ta có thể giả định rằng số nguyên không chứa bất kỳ số 0 nào đứng đầu, ngoại trừ chính số 0. Trong danh sách được liên kết, chữ số quan trọng nhất nằm ở đầu danh sách.

Vì vậy, nếu đầu vào là [1,2,3], thì đầu ra sẽ là [1,2,4]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu phần đầu là rỗng, thì -

  • quay trở lại đầu

• curr =đầu

• req =NULL

• trong khi curr khác 0, do -

  • nếu val của curr không bằng 9 thì -

    • req:=curr

  • curr:=next of curr

• nếu không yêu cầu khác 0, thì -

  • dummy =nút mới với giá trị 1

  • tiếp theo của dummy:=head

  • trong khi head khác 0, do -

    • val of head:=0

    • head:=next of head

  • trả lại hình nộm

• Nếu không

  • tăng giá trị yêu cầu lên 1

  • req:=next of req

  • trong khi yêu cầu khác 0, hãy làm -

    • giá trị của yêu cầu:=0

    • req:=next of req

  • quay trở lại đầu

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn.

#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;
      }
   }
};
main(){
   Solution ob;
   vector<int< v = {1,4,5};
   ListNode *head = make_list(v);
   print_list(ob.plusOne(head));
}

Đầu vào

{1,4,5}

Đầu ra

[1, 4, 6, ]