0%

leetcode之旅-02-两数相加

Posted on Edited on In

1. 题目描述

题目描述

  • 概述：两个逆序存储的非零开头的数字链表，求两数之和，输出也是逆序的链表

  • leetcode 01 02两个题分别考察了列表在物理存储层面的两种表示方式：数组和链表 的加法

    2. 我的解法

    暴力：按顺序同时遍历两个链表，按照进位规则进行加法运算，同时需要注意两个数维数不等，以及结果可能维数增加的情况 我的问题是，代码太过复杂：
    • a. 在初始化L3时，由于不是控制，需要另外计算存储值。应该设立空的表头，放到循环中值。
    • b. 在循环之外，分别判断了当两个值不等长时的情况，可以归并到循环中，减少代码函数
      1
       /* Definition for singly-linked list.
      2
       * public class ListNode {
      3
       *     int val;
      4
       *     ListNode next;
      5
       *     ListNode(int x) { val = x; }
      6
       * }
      7
       */
      8
      class Solution {
      9
          public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      10
              int num=l1.val+l2.val;
      11
              ListNode l3 =new ListNode(num%10); 
      12
              ListNode head=l3;
      13
              //同时遍历两个链表
      14
              while(l1.next!=null&&l2.next!=null)
      15
              {
      16
                  l1=l1.next;
      17
                  l2=l2.next;
      18
                  num=l1.val+l2.val+num/10;//加上进位
      19
                  l3.next=new ListNode(num%10);//超出10，求余
      20
                  l3=l3.next;
      21
              }
      22
              //如果两个链表不等长，即两个数位数不同，剩下的分别遍历
      23
              while(l1.next!=null)
      24
              {
      25
                  l1=l1.next;
      26
                  num=l1.val+num/10;
      27
                  l3.next=new ListNode(num%10);
      28
                  l3=l3.next;
      29
              }
      30
              while(l2.next!=null)
      31
              {
      32
                  l2=l2.next;
      33
                  num=l2.val+num/10;
      34
                  l3.next=new ListNode(num%10);
      35
                  l3=l3.next;
      36
              }
      37
              //最后如果相加多出一位，别忘了加上
      38
              if(num/10!=0)
      39
                  l3.next=new ListNode(num/10);
      40
              return head;
      41
          }
      42
      		}
  • 时间复杂度：O(max(m,n))
  • 空间复杂度： O(max(m,n))

    3. 解法二

    解决我的解法的问题
    1
    class ListNode {
    2
        int val;
    3
        ListNode next;
    4
        ListNode(int x) { val = x; }
    5
    }
    6
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    7
        ListNode dummyHead = new ListNode(0);//设置空的链表头
    8
        ListNode p = l1, q = l2, curr = dummyHead;
    9
        int carry = 0;
    10
        while (p != null || q != null) {
    11
            int x = (p != null) ? p.val : 0;//当不等长时，补充相应值0
    12
            int y = (q != null) ? q.val : 0;
    13
            int sum = carry + x + y;
    14
            carry = sum / 10;
    15
            curr.next = new ListNode(sum % 10);
    16
            curr = curr.next;
    17
            if (p != null) p = p.next;
    18
            if (q != null) q = q.next;
    19
        }
    20
        if (carry > 0) {
    21
            curr.next = new ListNode(carry);
    22
        }
    23
        return dummyHead.next;
    24
    }

  • 时空复杂度不变

    3. 扩展

    如果链表存储的顺序反过来怎么办？
    我首先想到的是链表先逆序计算，然后将结果再逆序呗，这就转换到我们之前的情况了。不知道还有没有其他的解法。

  • 3.1 下边是单链表逆序的代码。

1
//逆序
2
   	ListNode pre = null;
3
     ListNode head = node;
4
     while(head!=null)
5
     {
6
         ListNode next = head.next;//保留下一个节点，防丢失
7
         head.next =pre;//新head接上
8
         pre = head;//pre指针指向新head
9
         head = next;//原列表更换head
10
     }
  • 3.2 递归思路，单列表逆序
    1
    public ListNode reverseListRecursion(ListNode head) {
    2
            ListNode newHead;
    3
            if(head==null||head.next==null ){
    4
                return head;
    5
            }
    6
            newHead=reverseListRecursion(head.next); 
    7
            head.next.next=head; //目前的head.next指向newhead的最后一个节点
    8
            head.next=null;
    9
            return newHead;
    10
        }

    4. 参考列表

  1. 题解-wang