reverse two LinkedLists and sum them together, let's solve the problems '2. Add Two Numbers' , '206. Reverse Linked List' and '445. Add Two Numbers II'
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1: Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Answer
While Interator
var addTwoNumbers = function(l1, l2) {
let p1 = l1, p2 = l2, carry = 0
const pHead = p = new ListNode()
while (p1 || p2) {
const v1 = p1 ? p1.val : 0
const v2 = p2 ? p2.val : 0
p = p.next = new ListNode((v1 + v2 + carry) % 10)
carry = (v1 + v2 + carry) / 10 | 0
if (p1) p1 = p1.next
if (p2) p2 = p2.next
}
if (carry) p.next = new ListNode(1)
return pHead.next
};
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
p1, p2, p, carry := l1, l2, &ListNode{}, 0
pHead := p
for p1 != nil || p2 != nil {
sum := carry
if p1 != nil {
sum += p1.Val
}
if p2 != nil {
sum += p2.Val
}
p.Next = &ListNode{Val: sum % 10}
p = p.Next
carry = sum / 10
if p1 != nil {
p1 = p1.Next
}
if p2 != nil {
p2 = p2.Next
}
}
if carry == 1 {
p.Next = &ListNode{Val: 1}
}
return pHead.Next
}
class Solution {
function addTwoNumbers($l1, $l2) {
$p1 = $l1;
$p2 = $l2;
$carry = 0;
$pHead = $p = new ListNode();
while ($p1 || $p2) {
$sum = $carry;
if ($p1) $sum += $p1->val;
if ($p2) $sum += $p2->val;
$p = $p->next = new ListNode($sum % 10);
$carry = $sum / 10 | 0;
if ($p1) $p1 = $p1->next;
if ($p2) $p2 = $p2->next;
}
if ($carry) $p->next = new ListNode(1);
return $pHead->next;
}
}
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1, p2 = l2, pHead = new ListNode(-1), p = pHead;
int carry = 0;
while (p1 != null || p2 != null) {
int sum = carry;
if (p1 != null) sum += p1.val;
if (p2 != null) sum += p2.val;
p = p.next = new ListNode(sum % 10);
carry = sum / 10;
if (p1 != null) p1 = p1.next;
if (p2 != null) p2 = p2.next;
}
if (carry == 1) p.next = new ListNode(1);
return pHead.next;
}
}
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1, p2 = l2, pHead = new ListNode(), p = pHead;
int carry = 0;
while (p1 != null || p2 != null) {
int sum = carry;
if (p1 != null) sum += p1.val;
if (p2 != null) sum += p2.val;
p = p.next = new ListNode(sum % 10);
carry = sum / 10;
if (p1 != null) p1 = p1.next;
if (p2 != null) p2 = p2.next;
}
if (carry == 1) p.next = new ListNode(1);
return pHead.next;
}
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* pHead = new ListNode();
ListNode* p = pHead;
int carry = 0;
while (l1 != nullptr || l2 != nullptr) {
int sum = carry;
if (l1) sum += l1->val;
if (l2) sum += l2->val;
p = p->next = new ListNode(sum % 10);
carry = sum / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry) p->next = new ListNode(1);
return pHead->next;
}
};
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* p1 = l1;
struct ListNode* p2 = l2;
struct ListNode* p = NULL;
p = malloc(sizeof(struct ListNode));
p->val = 1;
p->next = NULL;
struct ListNode* pHead = p;
int carry = 0;
while (p1 || p2) {
int sum = carry;
if (p1) sum += p1->val;
if (p2) sum += p2->val;
p->next = malloc(sizeof(struct ListNode));
p->next->val = sum % 10;
p->next->next = NULL;
p = p->next;
carry = sum / 10;
if (p1) p1 = p1->next;
if (p2) p2 = p2->next;
}
if (carry == 1) {
p->next = malloc(sizeof(struct ListNode));
p->next->val = 1;
p->next->next = NULL;
}
return pHead->next;
}
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
p1, p2, p, carry = l1, l2, ListNode(-1), 0
pHead = p
while p1 or p2:
total = carry
if p1: total += p1.val
if p2: total += p2.val
p.next = ListNode(total % 10)
p = p.next
carry = total // 10
if p1: p1 = p1.next
if p2: p2 = p2.next
if carry == 1: p.next = ListNode(1)
return pHead.next
Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1:
Input：head = [1,2,3,4,5] Output：[5,4,3,2,1]
Answer
Dummy Node
Declare a dummy node prev, cache the current node's next, then make the current node's next point to prev, the move prev to point to the current node and the current to point to the cached next node.
var reverseList = function(head) {
var prev = null
while (head) {
const next = head.next
head.next = prev
prev = head
head = next
}
return prev
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
class Solution {
function reverseList($head) {
$prev = null;
while ($head) {
$next = $head->next;
$head->next = $prev;
$prev = $head;
$head = $next;
}
return $prev;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
};
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
next = head.next
head.next = prev
prev = head
head = next
return prev
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1:
const reverse = head => {
let prev = null
while (head !== null) {
const next = head.next
head.next = prev
prev = head
head = next
}
return prev
}
var addTwoNumbers = function(l1, l2) {
const pHead = new ListNode()
let p = pHead, p1 = reverse(l1), p2 = reverse(l2), carry = 0
while (p1 !== null || p2 !== null) {
let sum = carry
if (p1) sum += p1.val
if (p2) sum += p2.val
p = p.next = new ListNode(sum % 10)
carry = sum / 10 | 0
if (p1) p1 = p1.next
if (p2) p2 = p2.next
}
if (carry) p.next = new ListNode(1)
return reverse(pHead.next)
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
p1, p2, pHead, carry := reverse(l1), reverse(l2), &ListNode{}, 0
p := pHead
for p1 != nil || p2 != nil {
sum := carry
if p1 != nil {
sum += p1.Val
}
if p2 != nil {
sum += p2.Val
}
p.Next = &ListNode{sum % 10, nil}
carry = sum / 10
p = p.Next
if p1 != nil {
p1 = p1.Next
}
if p2 != nil {
p2 = p2.Next
}
}
if carry == 1 {
p.Next = &ListNode{1, nil}
}
return reverse(pHead.Next)
}
class Solution {
function reverse($head) {
$prev = null;
while ($head) {
$next = $head->next;
$head->next = $prev;
$prev = $head;
$head = $next;
}
return $prev;
}
function addTwoNumbers($l1, $l2) {
$p = $pHead = new ListNode();
$l1 = $this->reverse($l1);
$l2 = $this->reverse($l2);
$carry = 0;
while ($l1 != null || $l2 != null) {
$sum = $carry;
if ($l1) $sum += $l1->val;
if ($l2) $sum += $l2->val;
$p = $p->next = new ListNode($sum % 10);
$carry = $sum / 10 | 0;
if ($l1) $l1 = $l1->next;
if ($l2) $l2 = $l2->next;
}
if ($carry == 1) $p->next = new ListNode(1);
return $this->reverse($pHead->next);
}
}
class Solution {
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode p = new ListNode(), pHead = p;
int carry = 0;
while (l1 != null || l2 != null) {
int sum = carry;
if (l1 != null) sum += l1.val;
if (l2 != null) sum += l2.val;
p = p.next = new ListNode(sum % 10);
carry = sum / 10 | 0;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry == 1) p.next = new ListNode(1);
return reverse(pHead.next);
}
}
public class Solution {
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode pHead = new ListNode();
ListNode p = pHead;
int carry = 0;
while (l1 != null || l2 != null) {
int sum = carry;
if (l1 != null) sum += l1.val;
if (l2 != null) sum += l2.val;
p = p.next = new ListNode(sum % 10);
carry = sum / 10 | 0;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry == 1) p.next = new ListNode(1);
return reverse(pHead.next);
}
}
class Solution {
public:
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* pHead = new ListNode();
ListNode* p = pHead;
l1 = reverse(l1);
l2 = reverse(l2);
int carry = 0;
while (l1 != nullptr || l2 != nullptr) {
int sum = carry;
if (l1 != nullptr) sum += l1->val;
if (l2 != nullptr) sum += l2->val;
p = p->next = new ListNode(sum % 10);
carry = sum / 10;
if (l1 != nullptr) l1 = l1->next;
if (l2 != nullptr) l2 = l2->next;
}
if (carry == 1) p->next = new ListNode(1);
return reverse(pHead->next);
}
};
struct ListNode* reverse(struct ListNode* head) {
struct ListNode* prev = NULL;
while (head) {
struct ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* pHead = malloc(sizeof(struct ListNode));
struct ListNode* p = pHead;
l1 = reverse(l1);
l2 = reverse(l2);
int carry = 0;
while (l1 != NULL || l2 != NULL) {
int sum = carry;
if (l1) sum += l1->val;
if (l2) sum += l2->val;
p->next = malloc(sizeof(struct ListNode));
p->next->val = sum % 10;
p->next->next = NULL;
p = p->next;
carry = sum / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry == 1) {
p->next = malloc(sizeof(struct ListNode));
p->next->val = 1;
p->next->next = NULL;
}
return reverse(pHead->next);
}
class Solution:
def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
while head != None:
next = head.next
head.next = prev
prev = head
head = next
return prev
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
pHead = p = ListNode()
l1, l2, total, carry = self.reverse(l1), self.reverse(l2), 0, 0
while l1 or l2:
total = carry
if l1 != None: total += l1.val
if l2 != None: total += l2.val
p.next = ListNode(total % 10)
p = p.next
carry = total // 10
if l1 != None: l1 = l1.next
if l2 != None: l2 = l2.next
if carry == 1: p.next = ListNode(1)
return self.reverse(pHead.next)
