首页 > 代码库 > CTCI 2.5
CTCI 2.5
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the Ts digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input:(7-> 1 -> 6) + (5 -> 9 -> 2).Thatis,617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
Output: 9 -> 1 -> 2.That is, 912.
Simple simulation. Use a var to recourd if there is a carry. Rember add a new node to the list if after the iteration, the carry is 1. To handle the follow up, we could reverse the list first and then add them, then reverse the result back.
/* Iterate two list and add the two node, until reach one‘s end, then iterate the other one to the end.Use a var to record if the two number‘s sum is equal or greater than 10, if it is, add one to the next sum.Be careful when moved to the end, check the var to make sure if we need to add an additional node with number1 or not. The time complexity is O(N) and space complexity is O(N). We could ask if we could destroy the longerlist, then the space compleixty could be reduced to O(1). Facing the follow up, the most naive way is first reverse two list and then add them, then reverse the result.*/public class AddTwoNumber { public Node add(Node num1, Node num2) { if(num1 == null || num2 == null) return null; Node head = new Node(0); int bit = 0, num = 0; Node temp1 = num1, temp2 = num2, temp = head; while(temp1 != null && temp2 != null) { num = temp1.val + temp2.val + bit; temp1 = temp1.next; temp2 = temp2.next; bit = num / 10; Node node = new Node(num % 10); temp.next = node; temp = temp.next; } if(temp1 != null) { while(temp1 != null) { num = temp1.val + bit; temp1 = temp1.next; bit = num / 10; Node node = new Node(num % 10); temp.next = node; temp = temp.next; } } else { while(temp2 != null) { num = temp2.val + bit; temp2 = temp2.next; bit = num / 10; Node node = new Node(num % 10); temp.next = node; temp = temp.next; } } if(bit != 0) { Node node = new Node(bit); temp.next = node; } return head.next; } public void print(Node head) { Node temp = head; while(temp != null) { System.out.print(temp.val); temp = temp.next; } System.out.println(""); } public Node reverse(Node num) { Node node = new Node(0); Node temp1 = num, temp2 = num; while(temp1 != null) { temp2 = temp1.next; temp1.next = node.next; node.next = temp1; temp1 = temp2; } return node.next; } public Node addReverse(Node num1, Node num2) { Node rnum1 = reverse(num1); Node rnum2 = reverse(num2); return(reverse(add(rnum1, rnum2))); } public static void main(String[] args) { Node node1 = new Node(7); Node node2 = new Node(1); Node node3 = new Node(6); Node node11 = new Node(5); Node node22 = new Node(9); Node node33 = new Node(2); node1.next = node2; node2.next = node3; node11.next = node22; node22.next = node33; Node node111 = new Node(1); Node node4 = new Node(9); Node node5 = new Node(9); node4.next = node5; AddTwoNumber atn = new AddTwoNumber(); atn.print(atn.addReverse(node1, node11)); }}