FilesExpand file tree

 master

/

AddTwoNumbersII_445.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (62 loc) · 2.02 KB

 master

/

AddTwoNumbersII_445.java

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (62 loc) · 2.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

package Lists;

import java.util.Stack;

/**

* 两个非负数相加

* 要考虑边界情况，考虑和为0或和超过范围 （大数问题）

*/

public class AddTwoNumbersII_445 {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

Stack<Integer> stack1=new Stack<>();

Stack<Integer> stack2=new Stack<>();

while (l1!=null){

stack1.push(l1.val);

l1=l1.next;

}

while (l2!=null){

stack2.push(l2.val);

l2=l2.next;

}

ListNode Dummy=new ListNode();

Dummy.next=null;

int carry=0;

while (carry!=0||!stack1.isEmpty()||!stack2.isEmpty()){

int m=0;//m为单位计算的结果

if(!stack1.isEmpty()&&!stack2.isEmpty())

m=stack1.pop()+stack2.pop()+carry;//当两者都非空时，两者数加上进位

else if(!stack1.isEmpty()) m=stack1.pop()+carry;//当一个为空时，单个数加进位

else if(!stack2.isEmpty()) m=stack2.pop()+carry;

else m=carry;//都空时，进位为此时的结果

carry=0;

ListNode p=new ListNode(m%10);//新建结点，头插法

p.next=Dummy.next;

Dummy.next=p;

if(m>=10) carry=1;//大于等于10就有进位

}

return Dummy.next;

}

//未考虑超出int表示的范围情况

public ListNode addTwoNumbers_1(ListNode l1, ListNode l2) {

int num1=0;

int num2=0;

while (l1!=null){

num1=10*num1+l1.val;

l1=l1.next;

}

while (l2!=null){

num2=10*num2+l2.val;

l2=l2.next;

}

int sum=num1+num2;

if(sum==0) return new ListNode(0);//特殊情况

ListNode Dummy=new ListNode();

Dummy.next=null;

while (sum!=0){//头插法

int value=sum%10;

sum/=10;

ListNode p=new ListNode(value);

p.next=Dummy.next;

Dummy.next=p;

}

return Dummy.next;

}

}