关于java:牛客网高频算法题系列BM11链表相加二

29次阅读

共计 1578 个字符，预计需要花费 4 分钟才能阅读完成。

假如链表中每一个节点的值都在 0 – 9 之间，那么链表整体就能够代表一个整数。给定两个这种链表，请生成代表两个整数相加值的后果链表。

原题目见：BM11 链表相加 (二)

首先，非凡状况判断：

如果链表一为空，则间接返回链表二

如果链表二为空，则间接返回链表一

否则，应用 2 个栈用来寄存两个链表的结点：

首先将两个链表中的结点增加到栈中；

遍历 2 个栈，即执行加法，将值增加到新的栈中这样能够按倒序进行结点值相加，其中须要应用一个变量记录进位值；

须要留神的是，遍历完结后，须要依据进位值判断是否须要增加额定的结点；

最初，依据新的栈结构相加后的链表并返回之。

如果不想应用多余的栈空间，能够思考先将两个链表倒序排列后，再执行加法。

import java.util.Stack;

public class Bm011 {

    /**
     * 链表相加：应用栈
     *
     * @param head1 ListNode 类
     * @param head2 ListNode 类
     * @return ListNode 类
     */
    public static ListNode addInList(ListNode head1, ListNode head2) {
        // 如果链表一为空，则间接返回链表二
        if (head1 == null) {return head2;}
        // 如果链表二为空，则间接返回链表一
        if (head2 == null) {return head1;}
        // 2 个栈用来寄存两个链表的结点
        Stack<ListNode> nodes1 = new Stack<>();
        Stack<ListNode> nodes2 = new Stack<>();
        while (head1 != null) {nodes1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {nodes2.push(head2);
            head2 = head2.next;
        }

        // 记录进位值
        int addOne = 0;
        Stack<Integer> newNodes = new Stack<>();
        // 遍历栈，即执行加法，将值增加到新的栈中
        while (!nodes1.isEmpty() || !nodes2.isEmpty()) {
            int val1 = 0, val2 = 0, newVal = 0;
            if (!nodes1.isEmpty()) {val1 += nodes1.pop().val;
            }
            if (!nodes2.isEmpty()) {val2 += nodes2.pop().val;
            }
            newVal += addOne + val1 + val2;
            if (newVal > 9) {
                newVal = newVal % 10;
                addOne = 1;
            } else {addOne = 0;}
            newNodes.push(newVal);
        }
        if (addOne == 1) {newNodes.push(1);
        }
        ListNode newHead = new ListNode(-1);
        ListNode next = newHead;
        while (!newNodes.isEmpty()) {next.next = new ListNode(newNodes.pop());
            next = next.next;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        // 链表一：1 -> 3 -> 5
        ListNode head1 = ListNode.testCase3();
        // 链表二：2 -> 4 -> 6
        ListNode head2 = ListNode.testCase4();

        // 测试用例，冀望输入：3 -> 8 -> 1
        ListNode.print(addInList(head1, head2));
    }
}