文章目录
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
很基础的链表操作题目,一次循环依次对节点进行加法运算即可,要注意进位与边界条件,时间复杂度O(n)
为了可理解性,在我的实现中把加法与进位运算拆开分别处理了:
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 public ListNode addTwoNumbers (ListNode l1, ListNode l2) { if (l1 == null || l2 == null ) { return l1 == null ? l2 : l1; } ListNode p = new ListNode(l1.val + l2.val); ListNode head = p; while (l1.next != null && l2.next != null ) { l1 = l1.next; l2 = l2.next; p.next = new ListNode(l1.val + l2.val); p = p.next; } l1 = l1.next; l2 = l2.next; p.next = l1 == null ? l2 : l1; p = head; while (p != null ) { if (p.val > 9 ) { if (p.next == null ) { p.next = new ListNode(p.val / 10 ); } else { p.next.val += p.val / 10 ; } p.val %= 10 ; } p = p.next; } return head; }