首页 > 代码库 > [leetcode]Add Two Numbers

[leetcode]Add Two Numbers

2024-07-13 15:45:51   215人阅读

Add Two Numbers

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

 

算法思路：

思路1：

将两个因数转换成整型，求出和，再将和转换为链表形式

【注意】这个int类型会溢出，严格来说，long也会溢出，因此是不严谨的。

代码如下：

 1 public class Solution {   2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 3             if(l1 == null) return l2; 4             if(l2 == null) return l1; 5             return num2List( getNum(l1)  + getNum(l2));     6         } 7         private long getNum(ListNode l){ 8             if(l == null) return 0; 9             long num = 0;10             long length = 0;11             while( l != null){12                 num += Math.pow(10,length) * l.val;13                 length++;14                 l = l.next;15             }16             return num;17         }18         private ListNode num2List(long num){19             ListNode hhead = new ListNode(0);20             ListNode tail = hhead;21             if(num == 0) return hhead;22             while(num != 0){23                 ListNode tem = new ListNode((int)(num % 10));24                 tail.next = tem;25                 tail = tail.next;26                 num /= 10;27             }28             return hhead.next;29         }30 }
View Code

 

思路2：

直接在两个list中进行加和操作。模拟加法。

 1 public class Solution { 2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 3         if(l1 == null) return l2; 4         if(l2 == null) return l1; 5         int l1Length = getLength(l1),l2Length = getLength(l2); 6         if(l1Length > l2Length) return addTwoNumbers(l2, l1); 7         ListNode l2Pointer = l2; 8         ListNode l1Pointer = l1; 9         while(l2Pointer != null){10             l2Pointer.val = l2Pointer.val + ((l1Pointer == null) ? 0 : l1Pointer.val);11             if(l2Pointer.val > 9){12                 l2Pointer.val -= 10 ;13                 if(l2Pointer.next == null){14                     ListNode tail = new ListNode(1);15                     l2Pointer.next = tail;16                     break;17                 }18                 l2Pointer.next.val++;19             }20             l2Pointer = l2Pointer.next;21             if(l1Pointer != null)l1Pointer = l1Pointer.next;22         }23         return l2;24     }25     private int getLength(ListNode list){26         int length = 0;27         while(list != null){28             length++;29             list = list.next;30         }31         return length;32     }33 }


联系
我们