LintCode领扣算法问题答案：221. 链表求和 II

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LintCode领扣算法问题答案：221. 链表求和 II，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1801字，纯文字阅读大概需要3分钟。

内容图文

221. 链表求和 II

描述

假定用链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字顺序排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。

样例 1：

输入: 
	6->1->7   2->9->5
输出: 
	9->1->2

样例 2：

输入: 
	1->2->3   4->5->6
输出: 
	5->7->9

原题传送门

---

文章目录

• 221. 链表求和 II
• • 描述
  • 样例 1：
  • 样例 2：
• 题解
• 最后说两句
• 声明

---

题解

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param l1: The first list.
     * @param l2: The second list.
     * @return: the sum list of l1 and l2.
     */
    public ListNode addLists2(ListNode l1, ListNode l2) {
        // write your code here
    
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        Deque<ListNode> s1 = new LinkedList<>();
        while (l1 != null) {
            s1.push(l1);
            l1 = l1.next;
        }

        Deque<ListNode> s2 = new LinkedList<>();
        while (l2 != null) {
            s2.push(l2);
            l2 = l2.next;
        }

        ListNode h = new ListNode(0);
        // tail
        ListNode t = h;
        // last one
        ListNode l = t;

        while (!s1.isEmpty()
                || !s2.isEmpty()) {
            int v1 = 0;
            int v2 = 0;
            if (!s1.isEmpty()) {
                v1 = s1.pop().val;
            }
            if (!s2.isEmpty()) {
                v2 = s2.pop().val;
            }
            t.val += v1 + v2;
            if (t.val > 9) {
                t.next = new ListNode(1);
                t.val %= 10;
            } else {
                t.next = new ListNode(0);
            }
            l = t;
            t = t.next;
        }

        if (t.val == 0) {
            l.next = null;
        }

        h = this.reverse(h);

        return h;
    }

    private ListNode reverse(ListNode l) {
        Deque<ListNode> stack = new LinkedList<>();

        ListNode h = l;
        while (h.next != null) {
            stack.push(h);
            h = h.next;
        }

        ListNode t = h;
        while (!stack.isEmpty()) {
            t.next = stack.pop();
            t = t.next;
        }
        t.next = null;

        return h;
    }
}

最后说两句

非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~

作者水平有限，如果文章内容有不准确的地方，请指正。

希望小伙伴们都能每天进步一点点。

声明

本文由二当家的白帽子博客原创，转载请注明来源，谢谢~

内容总结

以上是互联网集市为您收集整理的LintCode领扣算法问题答案：221. 链表求和 II全部内容，希望文章能够帮你解决LintCode领扣算法问题答案：221. 链表求和 II所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---