1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public ListNode reverseList(ListNode pHead){

		if(pHead == null){
			return null;
		}
		ListNode pre = null;
		ListNode cur = pHead;
		ListNode next = pHead;

		while(cur!=null){
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}

		return pre;
	}
    
    public ListNode addInList (ListNode head1, ListNode head2) {
    // 链表1为空，直接返回链表2
    if (head1 == null) {
        return head2;
    }
    // 链表2为空，直接返回链表1
    if (head2 == null) {
        return head1;
    }

    // 反转两个链表，让低位在前（方便从低位开始相加）
    head1 = reverseList(head1);
    head2 = reverseList(head2);

    ListNode dummy = new ListNode(-1);  // 虚拟头节点：简化结果链表的头节点处理
    ListNode head = dummy;              // 结果链表的当前指针（用于挂载新节点）
    int carry = 0;                      // 进位标志

    // head1未遍历完 || head2未遍历完 || 还有进位（包含carry!=0，处理最后一位相加的进位）
    while (head1 != null || head2 != null || carry != 0) {
        // 获取当前节点的值（链表已遍历完则取0，不影响相加结果）
        int val1 = head1 == null ? 0 : head1.val;
        int val2 = head2 == null ? 0 : head2.val;

        int temp = val1 + val2 + carry;
        carry = temp / 10;  // 更新进位
        temp %= 10;         // 取当前位的结果

        // 创建当前位的节点，挂载到结果链表上
        head.next = new ListNode(temp);
        head = head.next;   // 结果链表指针后移，准备挂载下一个节点

        // 原链表指针后移
        if (head1 != null) {
            head1 = head1.next;
        }
        if (head2 != null) {
            head2 = head2.next;
        }
    }

    // 反转结果链表，恢复高位在前的格式，返回最终结果
    return reverseList(dummy.next);
}