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

ゞ浴缸里的玫瑰 2024-02-19 11:35 13阅读 0赞

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照顺序的方式存储的，并且每个节点只能存储一位数字。  
请你将两个数相减，并以相同形式返回一个表示相减结果的链表。  
你可以假设  
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; // 返回新链表
        }
    }