两个链表生成相加链表

我就是我 2022-12-04 01:21 150阅读 0赞

# 两个链表生成相加链表 #

## 1、参考资料 ##

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

## 2、题目要求 ##

> 题目描述

假设链表中每一个节点的值都在 `0 - 9` 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 `1` 为 `9->3->7`，链表 `2` 为 `6->3`，最后生成新的结果链表为 `1->0->0->0`。

> **示例1**

输入

[9,3,7],[6,3]

输出

{1,0,0,0}

## 3、代码思路 ##

这道题和 `LeetCode` 上面链表相加的题类似，只不过 `LeetCode` 上将低位排在链表的前面，高位排在链表的后面(比如 `3 --> 2 --> 1 --> null` 表示数字 `123`)，虽然不符合任何阅读习惯，但可以直接通过一次遍历求出两个链表的和；而这道题将高位排在链表的前面，低位排在链表的后面(比如 `1 --> 2 --> 3 --> null` 表示数字 `123`)，符合人的阅读习惯，但是却不方便我们遍历操作

能把数据顺序反过来的数据结构，那不就是栈嘛，我们可以先将两个链表中的数存储在链表中，计算的时候依次出栈，再加上一个标志位 `carry`，我们就能做到计算个位的和，并向十位进位，再计算十位的和，并向百位进位，以此类推。。。

不过在牛客上，因为超时只能有 `75%` 的通过率，看了评论区，据说 `Java` 都是这样，同样的思路用 `C++` 写就能 `AC`

## 4、代码实现 ##

代码

public static class Solution {
        
        public ListNode addInList(ListNode head1, ListNode head2) {
        
            ListNode list1Pointer = head1;
            ListNode list2Pointer = head2;
    
            LinkedList<Integer> stack1 = new LinkedList<>();
            LinkedList<Integer> stack2 = new LinkedList<>();
    
            // 将链表的数据添加至栈中
            while (list1Pointer != null || list2Pointer != null) {
        
                if (list1Pointer != null) {
        
                    stack1.push(list1Pointer.val);
                    list1Pointer = list1Pointer.next;
                }
                if (list2Pointer != null) {
        
                    stack2.push(list2Pointer.val);
                    list2Pointer = list2Pointer.next;
                }
            }
    
            int sum = 0; // 当前位的加和
            int carray = 0; // 进位标志位
            ListNode sumHead = null; // sumHead 永远是新链表的首节点
            // 加上 carray != 0 条件是因为：高位相加有可能需要向更高位进 1
            while ((stack1.isEmpty() == false) || (stack2.isEmpty() == false) || carray != 0) {
        
                sum = 0;
                if (stack1.isEmpty() == false) {
        
                    sum += stack1.pop();
                }
                if (stack2.isEmpty() == false) {
        
                    sum += stack2.pop();
                }
                sum += carray; // 加上上次的进位标志位
                carray = sum / 10; // 计算本次的进位标志位
                sum = sum % 10; // 计算当前位的加和
                ListNode curNode = new ListNode(sum);
                curNode.next = sumHead; // 当前节点指向之前的首节点
                sumHead = curNode; // 将链表首节点更新为当前节点
            }
    
            return sumHead;
        }
    }
    
    public static class ListNode {
        
        int val;
        ListNode next = null;
    
        public ListNode(int val) {
        
            this.val = val;
        }
    }