leetcode刷题两数相加（Java与C#）

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 1.Java 知识准备：链表相关知识： 链表的初始化：

public class Node<T> { public T data; public Node next; public Node(T data) { this.data = data; } }

链表的相关操作： 2.本题答案 方法1：官方给出的思路是利用初等数学的方法，

java public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } ```

方法2：链表

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode cur = pre; int carry = 0; while(l1 != null || l2 != null) { int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; int sum = x + y + carry; carry = sum / 10; sum = sum % 10; cur.next = new ListNode(sum); cur = cur.next; if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; } if(carry == 1) { cur.next = new ListNode(carry); } return pre.next; } } public class Solution { /// <summary> /// 累加两个数字（链表表示） /// </summary> /// <param name="l1">数字1</param> /// <param name="l2">数字2</param> /// <returns>两数之和（链表表示）</returns> public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode resultRoot = GetLongestList(l1, l2); //优化1：使用较长的一个数字空间来存储结果，减少内存分配 int overNumber = 0; //上一位数计算后的进位 ListNode currentResultNode = resultRoot; //初始化当前计算位数结果位（个位） ListNode lastNodeBackup = currentResultNode; //最后计算位数（最高位）位置备份 ListNode p_l1 = l1; //初始化数字1和数字2当前计算位数 ListNode p_l2 = l2; while (p_l1 != null || p_l2 != null || overNumber > 0) { int currentResult = (p_l1?.val ?? 0) + (p_l2?.val ?? 0) + overNumber; int realResult = currentResult % 10; currentResultNode.val = realResult; overNumber = currentResult == realResult ? 0 : 1; p_l1 = p_l1?.next; p_l2 = p_l2?.next; //优化2：如果其中一个数字较长，且与较短数字的所有位已计算完毕，且无进位，则将较长数字的后续位直接接到结果末尾，无需计算 if (p_l1 == null && p_l2 != null && overNumber == 0) { currentResultNode.next = p_l2; return resultRoot; } else if (p_l1 != null && p_l2 == null && overNumber == 0) { currentResultNode.next = p_l1; return resultRoot; } else { if (currentResultNode.next == null) { currentResultNode.next = new ListNode(0); } lastNodeBackup = currentResultNode; currentResultNode = currentResultNode.next; } } if (lastNodeBackup.next != null && lastNodeBackup.next.val == 0) { lastNodeBackup.next = null; //清除多余的0节点 } return resultRoot; } /// <summary> /// 返回较长的链表数字 /// </summary> /// <param name="l1">数字1</param> /// <param name="l2">数字2</param> /// <returns>两个数字中较长的数字</returns> private ListNode GetLongestList(ListNode l1, ListNode l2) { ListNode p_l1 = l1.next; ListNode p_l2 = l2.next; while (true) { if (p_l1 == null) { return l2; } else if (p_l2 == null) { return l1; } else { p_l1 = p_l1.next; p_l2 = p_l2.next; } } } }