【机试题】两个链表相减，并以相同形式返回一个表示相减结果的链表

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照顺序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相减，并以相同形式返回一个表示相减结果的链表。
你可以假设
1）除了数字 0 之外，这两个数都不会以 0 开头。
2）给定的第一数字一定比第二个数字大。
举例：
输入：l1 = [9,8,7], l2 = [5,1,2]
输出：[4,7,5]
解释：987-512 = 475

public class Test3 {

}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode subtractTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 创建一个虚拟头节点
        ListNode p1 = l1, p2 = l2; // 分别用p1和p2指向两个链表
        int carry = 0; // 初始化进位为0
        ListNode tail = dummy; // tail指向新链表的最后一个节点

        while (p1 != null || p2 != null) { // 当两个链表都不为空时
            int sub = (p1 != null) ? p1.val : 0 - (p2 != null) ? p2.val : 0 - carry; // 计算当前位的差值
            carry = Math.max(0, sub); // 计算进位
            tail.next = new ListNode(sub); // 将差值存储到新链表中
            tail = tail.next; // tail指向新链表的下一个节点
            p1 = p1 != null ? p1.next : null; // p1指向下一个节点
            p2 = p2 != null ? p2.next : null; // p2指向下一个节点
        }
        if (carry > 0) { // 如果还有进位，则需要在新链表的开头添加一个节点
            tail.next = new ListNode(carry);
        }
        return dummy.next; // 返回新链表
    }
}
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