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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode curNext = new ListNode(0);
        while (cur != null) {
            curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode newHead1 = reverse(head1);
        ListNode newHead2 = reverse(head2);
        int sum = 0;   // 本位和
        int count = 0; // 进位
        boolean flag = false;
        ListNode head = null;
        ListNode pHead = null;
        while (newHead1 != null && newHead2 != null) {
            int num = newHead1.val + newHead2.val + count;
            sum = num % 10;
            count = num / 10;
            if (!flag) {
                head = new ListNode(sum);
                pHead = head;
                flag = true;
            } else {
                ListNode cur = new ListNode(sum);
                head.next = cur;
                head = head.next;
            }
            newHead1 = newHead1.next;
            newHead2 = newHead2.next;
        }

        while (newHead1 != null) {
            int num = newHead1.val + count;
            sum = num % 10;
            count = num / 10;
            ListNode cur = new ListNode(sum);
            head.next = cur;
            head = head.next;
            newHead1 = newHead1.next;
        }
        while (newHead2 != null) {
            int num = newHead2.val + count;
            sum = num % 10;
            count = num / 10;
            ListNode cur = new ListNode(sum);
            head.next = cur;
            head = head.next;
            newHead2 = newHead2.next;
        }
        if (count == 1) {
            ListNode cur = new ListNode(count);
            head.next = cur;
        }
        return reverse(pHead);
    }
}

思路 : 当我们进行两个位数相加时,结果无非分为两部分,即本位和与进位和.反转链表,可以让我们从个位开始进行两个链表的相加.明确这两点之后,就可以尝试写代码:

1.先写如何反转单链表(此处写为一个子函数,返回反转后的单链表的头结点)

2.while循环,head1和head2都不能为空,因为我们要使用两个链表对应位置的值,即head1.val和head2.val,两数相加同时加上进位count(最开始肯定是0),即num = head1.val + head2.val + count.之后每次循环,count的值不断改变;

3.sum = num % 10 ; count = num / 10;

4.sum用于构造节点,count用于下一轮循环中计算对应和num .

5.出循环,表明至少一个链表走完,此时按相同逻辑走另外一个链表;

6.再出循环,表明两链表同时走完,此时若count为1,说明最后有一个进位,即需要再构造一个节点表示最高位为1.

7.翻转构造好的链表,返回翻转后的头结点,就是本题的结果!