LinkedList 添加两个数字：LeetCode

Question

给你两个非空链表，代表两个非负整数。这些数字以相反的顺序存储，并且每个节点都包含一个数字。将两个数字相加并以链表形式返回。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。

据我所知，链表似乎覆盖了节点。我确实在 GeeksforGeeks 上找到了这个问题的答案，但我需要帮助找出我的代码出了什么问题。我也知道我的代码在优化方面不是最好的，但任何暂停都是可以接受的。谢谢！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    class Solution {
        //ListNode head;
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int x = 0;
            int y = 0;
            int z = 1;
    
            while(l1 != null){
                x += z*l1.val;
                z*=10;
                l1 = l1.next;
            }
          
            z = 1;
            while(l2 != null){
                y += z*l2.val;
                z*=10;
                l2 = l2.next;
            }
    
            int sum = x + y;
            ListNode node = new ListNode(0);
            
            while(sum > 0){
                int digit = sum % 10;
                ListNode n = new ListNode(digit);
                while(node.next != null){
                    node = node.next;
                }
                node.next = n;
                
                sum = sum / 10;
    
                
            }      
            return node;
    
        }
    }

LeetCode问题

Answer 1

我喜欢你的解决方案，但你的逻辑有点不完整。

class Solution {
    //ListNode head;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int x = 0;
        int y = 0;
        int z = 1;

        while(l1 != null){
            x += z*l1.val;
            z*=10;
            l1 = l1.next;
        }

        z = 1;
        while(l2 != null){
            y += z*l2.val;
            z*=10;
            l2 = l2.next;
        }

        int sum = x + y;
        if (sum == 0) {
            return new ListNode(0);
        }

        ListNode node = null, head = null;
        while(sum > 0){
            int digit = sum % 10;
            ListNode n = new ListNode(digit);
            if (node == null) {
                head = node = n;
            } else {
                node.next = n;
                node = node.next;
            }
            
            sum = sum / 10;
        }

        return head;
    }
}

之后我只是改变了一两件事

int sum = x + y;

Answer 2

这是kotlin语言中的解决方案。

class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    
    var head1=l1
    var head2=l2

    var result:ListNode?=null
    var temp:ListNode?=null

    var carry=0

    while(head1 != null || head2 != null)
    {
        var sum=carry

       if(head1 != null)
       {

         sum +=  head1.`val`
         head1=head1.next

       }

       if(head2 != null)
       {
          sum +=head2.`val`
          head2= head2.next

       }
         
        val node= ListNode(sum%10)

        carry=sum/10

        if(temp== null)
        {

             result=node
             temp=result


        }

        else{ temp.next=node
        temp=temp.next}
       
    }

    if(carry>0){

        temp!!.next=ListNode(carry)
    }

return result
}
}

Answer 3

我提交的leetcode中的Java解决方案。在运行时击败 100% 的其他解决方案，在内存中击败 97.3% 的解决方案。当然它使用递归。

 /* Definition for singly-linked list.
 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }*/
 
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum, carry;
        sum = l1.val + l2.val;
        carry = 0;
        if (sum >= 10){
            sum = sum - 10;
            carry = 1;
        }
        l1.val = sum;
        if(carry == 1){
            if(l1.next != null) {
                l1.next.val++;
            }
            else {
                l1.next = new ListNode(carry);
            } 
        }
        if(l1.next != null && l2.next!= null) addTwoNumbers(l1.next, l2.next);
        else if (l1.next!= null && l2.next == null) addTwoNumbers(l1.next, new ListNode(0));
        else if (l2.next != null && l1.next == null) {
            l1.next = new ListNode(0);
            addTwoNumbers(l1.next, l2.next);
        }
        return l1;
    }
}

Answer 4

我提交的 leetcode 中的 PHP 解决方案。运行时间24ms，内存 19.16MB。

class ListNode {
        public $val;
        public $next;
    
        public function __construct($val = 0, $next = null) {
            $this->val = $val;
            $this->next = $next;
        }
    }
    
    function addTwoNumbers($l1, $l2) {
        $result = new ListNode(0);
        $current = $result;
        $carry = 0;
    
        while ($l1 != null || $l2 != null) {
            $val1 = ($l1 != null) ? $l1->val : 0;
            $val2 = ($l2 != null) ? $l2->val : 0;
            $sum = $val1 + $val2 + $carry;
    
            $carry = intdiv($sum, 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;
    
            if ($l1 != null) {
                $l1 = $l1->next;
            }
            if ($l2 != null) {
                $l2 = $l2->next;
            }
        }
    
        if ($carry > 0) {
            $current->next = new ListNode($carry);
        }
    
        return $result->next;
    }

'