1 题目
给定两个用链表表示的整数,每个节点包含一个数位。
这些数位是反向存放的,也就是个位排在链表首部。
编写函数对这两个整数求和,并用链表形式返回结果。
示例:
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢?
输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
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) { // write your code here // 如果 l1 为空直接返回l2 if (l1 == null) { return l2; } // 如果 l2 为空直接返回l1 if (l2 == null) { return l1; } // 两者都不为空,先默认返回 l1 ListNode result = l1; // resIndex 始终指向 l1 的最后一个节点 ListNode resIndex = l1; int carry = 0; while (l1 != null && l2 != null) { int num = l1.val + l2.val + carry; if (num > 9) { carry = 1; l1.val = num - 10; } else { carry = 0; l1.val = num; } // 向后移动 resIndex = l1; l1 = l1.next; l2 = l2.next; } // 到这里说明 l1 l2 至少有一个为空了 // 剩下的就是需要把那条不为空的接上来 while (l2 != null) { int num = l2.val + carry; if (resIndex.next == null) { resIndex.next = new ListNode(0); } if (num > 9) { carry = 1; resIndex.next.val = num - 10; } else { carry = 0; resIndex.next.val = num; } resIndex = resIndex.next; l2 = l2.next; } while (l1 != null) { int num = l1.val + carry; if (num > 9) { carry = 1; resIndex.next.val = num - 10; } else { carry = 0; resIndex.next.val = num; } resIndex = resIndex.next; l1 = l1.next; } // 不需要进位 直接返回result 就是 l1 if (carry <= 0) { return result; } // 需要进位 if (resIndex.next == null) { resIndex.next = new ListNode(1); } return result; } }
稍后我想想怎么优化,加油。