题解 | #链表相加(二)#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:

ListNode* reverse(ListNode* head) {
  ListNode* reverse = nullptr;
  ListNode* ptr = head;
  ListNode* cur;
  while (ptr) {
    cur = ptr;
    ptr = ptr->next;
    cur->next = reverse;
    reverse = cur;
  }
  return reverse;
}

int length(ListNode* list) {
  if (!list) return 0;
  int len = 0;
  ListNode* ptr = list;
  while (ptr) {
    len++;
    ptr = ptr->next;
  }
  return len;
}

ListNode* addInList(ListNode* head1, ListNode* head2) {
  if (!head1) return head2;
  if (!head2) return head1;

  head1 = reverse(head1);
  head2 = reverse(head2);

  decltype(head1) list1;
  decltype(head1) list2;
  // 关键就在于这个tail指针，指向了较长的链表的尾部，
  // 在第一段，即(ptr1 && ptr2)这一段：tail指向ptr1的尾部，
  // 在第二节点，即(ptr1 && !ptr2) 这一段同样指向ptr1的尾部
  // 是为了确保如果链表结束，而且carry进位位部位0的时候，尾部插入carry节点。
  decltype(head1) tail1;

  int diff = length(head1) - length(head2);
  if (diff != 0) {
    list1 = diff > 0 ? head1 : head2;
    list2 = diff > 0 ? head2 : head1;
  }

  auto ptr1 = list1;
  auto ptr2 = list2;
  int carry = 0;

  //   ptr1 长度 大于等于ptr2
  while (ptr1 && ptr2) {
    if (ptr1->next == nullptr) tail1 = ptr1;
    ptr1->val += (ptr2->val + carry);
    carry = ptr1->val / 10;
    ptr1->val %= 10;
    ptr1 = ptr1->next;
    ptr2 = ptr2->next;
  }

  if (diff == 0 && carry) {
    tail1->next = new ListNode(carry);
    return reverse(list1);
  }
  if (carry) {
    while (ptr1) {
      if(ptr1->next == nullptr) tail1 = ptr1;
      ptr1->val += carry;
      carry = ptr1->val / 10;
      ptr1->val %= 10;
      ptr1 = ptr1->next;
    }
    if (carry) {
      tail1->next = new ListNode(carry);
    }
  }
  return reverse(list1);
}

};