快手算法：链表求和 #114

Activity

1. sisterAn

   added

   快手

   on Sep 28, 2020
2. dinjufen commented on Sep 29, 2020

   

   dinjufen

   on Sep 29, 2020

   More actions

   用carry存储每次的进位

   var addTwoNumbers = function(l1, l2) {
       let carry = 0;
       let root = new ListNode(0)
       let p = root;
       while (l1 || l2) {
           let sum = 0
           if (l1) {
               sum += l1.val
               l1 = l1.next
           }
           if (l2) {
               sum += l2.val
               l2 = l2.next
           }
           sum += carry
           carry = Math.floor(sum / 10)
           p.next = new ListNode(sum % 10)
           p = p.next
       }
       if (carry === 1) {
           p.next = new ListNode(carry)
           p = p.next
       }
       return root.next
   };

   👍React with 👍2Reacted by 瓶子君 and yum
3. syc666 commented on Sep 29, 2020

   

   syc666

   on Sep 29, 2020

   Last edited by syc666

   More actions

   进阶部分，先把两个链表倒置，再相加

   function fn(l1, l2) {
       //函数导致
   	const reverseFn = (l) => {
   		let prev = null,
   			curr = l
   		while (curr) {
   			const temp = curr.next
   			curr.next = prev
   			prev = curr
   			curr = temp
   		}
   		return prev
   	}
   	const reverseL1 = reverseFn(l1)
       const reverseL2 = reverseFn(l2)
       
       //单个链表计算
   	const sumFn = (l) => {
   		let n = 1,
   			sum = 0
   		while (l) {
   			sum += n * l.val
   			l = l.next
   			n = n * 10
   		}
   		return sum
   	}
   	const res = sumFn(reverseL1) + sumFn(reverseL2)
   	return res
   }
4. MickWang commented on Oct 4, 2020

   

   MickWang

   on Oct 4, 2020

   More actions

   进阶部分，先把两个链表倒置，再相加

   function fn(l1, l2) {
       //函数导致
   	const reverseFn = (l) => {
   		let prev = null,
   			curr = l
   		while (curr) {
   			const temp = curr.next
   			curr.next = prev
   			prev = curr
   			curr = temp
   		}
   		return prev
   	}
   	const reverseL1 = reverseFn(l1)
       const reverseL2 = reverseFn(l2)
       
       //单个链表计算
   	const sumFn = (l) => {
   		let n = 1,
   			sum = 0
   		while (l) {
   			sum += n * l.val
   			l = l.next
   			n = n * 10
   		}
   		return sum
   	}
   	const res = sumFn(reverseL1) + sumFn(reverseL2)
   	return res
   }
   ``

   直接转化为数字相加在超过js数字精度时就不正确了
5. yangchongduo commented on Oct 12, 2020

   

   yangchongduo

   on Oct 12, 2020

   More actions

   也就是个位排在链表首部
   (7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
   个位 在链表首部 不是应该 716 + 592
6. AnranS commented on Nov 17, 2020

   

   AnranS

   on Nov 17, 2020

   More actions

   var addTwoNumbers = function (l1, l2) {
       let dump = new ListNode();
       let p1 = l1, p2 = l2, current = dump;
       // 进位标识
       let curry = 0;
       while (p1 && p2) {
           let res = p1.val + p2.val + curry;
           curry = 0;
           if (res >= 10) {
               curry = 1;
               current.next = new ListNode(res % 10);
           } else {
               current.next = new ListNode(res);
           }
           current = current.next;
           p1 = p1.next;
           p2 = p2.next;
       }
       let rest = p1 === null ? p2 : p1;
       while (rest) {
           let res = rest.val + curry;
           curry = 0;
           if (res >= 10) {
               curry = 1;
               current.next = new ListNode(res % 10);
           } else {
               current.next = new ListNode(res);
           }
           rest = rest.next;
           current = current.next;
       }
       if (curry) current.next = new ListNode(curry);
   
       return dump.next;
   };
7. Anoi1018 commented on Jan 29, 2021

   

   Anoi1018

   on Jan 29, 2021

   More actions

   var addTwoNumbers = function(l1, l2) {
   if(l1===null) return l2;
   if(l2===null) return l1;
   var carry = 0,sum=0,pre=new ListNode(0),p=pre,a,b;
   while(l1 || l2){
   a = l1===null? 0 : l1.val;
   b = l2===null? 0 : l2.val;
   sum = a+b+ carry;
   var node= new ListNode(sum%10);
   carry = (sum-sum%10)/10;
   p.next = node;
   p = node;
   if(l1) l1= l1.next;
   if(l2) l2= l2.next;
   }

   if(carry !== 0) p.next = new ListNode(carry);
   
   return pre.next; 
   

   };
8. JohnApache commented on Apr 27, 2021

   

   JohnApache

   on Apr 27, 2021

   Last edited by JohnApache

   More actions

   反向求和的情况
   利用了 递归回溯

   const addTwoNumbers = (list1: Node, list2: Node) => {
       let multy = 0;
       const fn = (next1: Node | undefined, next2: Node | undefined) => {
           if (!next1 && !next2) {
               return multy > 0 ? new Node(multy) : undefined;
           }
           const element = (next1 ? next1.element : 0) + (next2 ? next2.element : 0) + multy;
           multy = Math.floor(element / 10);
           const node = new Node(element - multy * 10);
           node.next = fn(next1?.next, next2?.next);
           return node;
       };
       return fn(list1, list2);
   };

   正向求和

   const addTwoNumbers2 = (list1: Node, list2: Node) => {
       let multy = 0;
       const fn = (next1: Node | undefined, next2: Node | undefined) => {
           if (!next1 && !next2) return undefined;
           const prevNode = fn(next1?.next, next2?.next);
           const element = (next1 ? next1.element : 0) + (next2 ? next2.element : 0) + multy;
           multy = Math.floor(element / 10);
           const node = new Node(element - multy * 10);
           node.next = prevNode;
           return node;
       };
       let result = fn(list1, list2);
       if (multy > 0) {
           const node = new Node(multy);
           node.next = result;
           result = node;
       }
       return result;
   };