最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天简讯:LeetCode.面试题02.05-链表求和-题解分析

来源：博客园

题目来源

面试题 02.05. 链表求和

题目详情

给定两个用链表表示的整数，每个节点包含一个数位。


【资料图】

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295输出：2 -> 1 -> 9，即912

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295输出：9 -> 1 -> 2，即912

题解分析

题目的要求是对链表的节点进行求和。题目的难点在于两个链表的长度可能不同，而且每个节点只能存放一个数位的元素。

这里最直接的解法就是模拟法，或者叫做遍历法，同时遍历这两个链表并进行加法运算，构造出一个新的结果链表。考虑到这里是一个反向链表，可以直接从头开始遍历，因此，这个题目也可以看成是一个子问题的题目即使用递归的思想解决。

使用递归的方法相对容易理解，而且写法比较简单。在每一轮递归的过程中，需要同时记录进位，在两个链表都遍历结束的时候，因为每个节点只能存放一个位的元素，因此可能会存在进位元素，需要放在一个新的尾部节点中。

java实现

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

关键词： 一个新的 结束的时候 从头开始