算法通关村第二关——链表加法的问题解析

缺乏、安全感 2024-03-22 22:19 57阅读 0赞

### 题目类型 ###

> 链表反转、栈

### 题目描述 ###

>     * 题目：
>     * 给你两个非空链表来表示两个非负整数，数字最高位位于链表的开始位置。
>     * 它们的每个节点都只存储一个数字。将这两个数相加会返回一个新的链表。
>     * 你可以假设除了数字0外，这两个数字都不会以0开头

#### 示例 ####

> 输入：6 --> 1 -->7 和 2 --> 9 -->5
> 
> 输出： 9 --> 1 --> 2

#### 实现方式 ####

> 栈
> 
> 反转链表

##### 栈实现 #####

###### 思路 ######

> 先将两个链表的元素分别压栈，然后再一起出栈，将两个结果分别计算。之后对计算的结果取模，模数保存到新的链表中，进位保存到下一轮，完成之后再进行一次反转就行了

###### 事项 ######

> 我们知道在链表插入有头插法和尾插法两种。头插法就是每次都将新的结点插到head之前。而尾插法就是将新结点都插入到链表的表尾。两者的区别是尾插法的顺序与原始链表是一致的，而头插法与原始链表是逆序的，所以上面最后步如果不想进行反转，可以将新结点以头插法

###### 代码实现 ######

/**
         *  使用栈实现两数相加
         * @param head1 第一个链表头节点
         * @param head2 第二个链表头节点
         * @return 相加后的到的链表头节点
         */
        public Node andTwoSingleListByStack(Node head1 , Node head2){
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            //  将链表节点数据入栈
            while (head1 != null){
                stack1.push(head1);
                head1 = head1.next;
            }
            while (head2 != null){
                stack2.push(head2);
                head2 = head2.next;
            }
            // 构造虚拟节点
            Node dummyNode = new Node(0);
            // carry 用于标识是否有进位
            int carry = 0;
    
            while (!stack1.empty() || !stack2.empty() || carry != 0){
                // 使用两个链表来存储栈中的数据
                Node a = new Node(0);
                Node b = new Node(0);
                if (!stack1.empty()){
                    a = stack1.pop();
                }
                if (! stack2.empty()){
                    b = stack2.pop();
                }
                int sum = a.data + b.data + carry;
                int ans = sum % 10;
                carry = sum / 10;
    
                Node cur = new Node(ans);
                cur.next = dummyNode.next;
                dummyNode.next = cur;
            }
            return dummyNode.next;
        }

##### 链表反转实现 #####

###### 思路 ######

> 先将两个链表分别反转，最后计算完之后再将结果反转，一共有三次反转操作

###### 代码实现 ######

public Node addTwoSingleListByReverseList(Node head1 , Node head2){
                // 反转链表，将低位放在表头，高位放在表尾
              head1 = reverseList(head1);
              head2 = reverseList(head2);
              // 定义虚拟节点
            Node dummyNode = new Node(0);
            Node cur = dummyNode;
            int carry = 0;
    
            while (head1 != null || head2 != null){
                int val = carry;
                if (head1 != null){
                    val += head1.data;
                    head1 = head1.next;
                }
                if (head2 != null){
                    val += head2.data;
                    head2 = head2.next;
                }
    
                int ans = val % 10;
                 carry = val / 10;
                cur.next = new Node(ans);
                cur = cur.next;
            }
    
            if (carry > 0 ){
                cur.next = new Node(carry);
            }
            return reverseList(dummyNode.next);
        }
    
        private Node reverseList(Node head){
            Node pre = null;
            Node cur = head;
            while (cur != null){
                Node next = cur.next;
                // 发生关系
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }

######  ######