2021-02-04 链表求和

题目地址

https://leetcode-cn.com/problems/sum-lists-lcci/

题目描述

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

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

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

示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

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

题解

这里给出进阶版的两个解答. 即

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即716 + 592
输出：1->3 -> 0 -> 8，即1308

思路1: 先把两个链表反转, 再逐个相加, 将和用尾插法创建新链表返回, 要注意进位情况.
思路2: 遍历两个链表, 将值存到栈里, 再遍历栈, 用尾插法创建新链表返回.
第二个思路明显更优, 少了链表反转的过程, 不更改原数据, 也更简洁.

/**
 * Created by zcdeng on 2021/2/4.
 */
public class TwoNodeListSum {
    public static void main(String[] args) {
        int[] nums1 = {6,9,4,5};
        int[] nums2 = {5,6};

        Node node1 = Node.createLinkedList(nums1);
        Node node2 = Node.createLinkedList(nums2);

        Node result = add2(node1, node2);
        Node.print(result);

        result = add(node1, node2);
        Node.print(result);
    }
    /**
     * 用两个栈存储两个链表的值, 然后用尾插法根据和创建新链表返回
     */
    private static Node add2(Node node1, Node node2) {
        List<Integer> stack1 = new ArrayList<Integer>();
        List<Integer> stack2 = new ArrayList<Integer>();
        while (node1 != null) {
            stack1.add(node1.getValue());
            node1 = node1.getNext();
        }
        while (node2 != null) {
            stack2.add(node2.getValue());
            node2 = node2.getNext();
        }
        Node newHead = new Node(-1);
        Node tmp = newHead;
        int up = 0;
        while (stack1.size() > 0 || stack2.size() > 0) {
            int sum = 0;
            if (stack1.size() > 0) {
                sum += stack1.remove(stack1.size() - 1);
            }

            if (stack2.size() > 0) {
                sum += stack2.remove(stack2.size() - 1);
            }
            sum += up;
            if (sum > 9) {
                up = sum / 10;
            }
            tmp = newHead.getNext();
            newHead.setNext(new Node(sum % 10));
            newHead.getNext().setNext(tmp);
        }

        if (up > 0) {
            tmp = newHead.getNext();
            newHead.setNext(new Node(up));
            newHead.getNext().setNext(tmp);
        }
        return newHead.getNext();
    }
    /**
     * 将两个链表反转后相加, 然后再反转
     */
    private static Node add(Node node1, Node node2) {
        Node reverse1 = reverseNodeList(node1);
        Node reverse2 = reverseNodeList(node2);

        Node newHead = new Node(-1);
        Node tmpHead = newHead;
        int up = 0;
        while (reverse1 != null || reverse2 != null) {
            int sum = 0;
            if (reverse1 != null) {
                sum += reverse1.getValue();
                reverse1 = reverse1.getNext();
            }

            if (reverse2 != null) {
                sum += reverse2.getValue();
                reverse2 = reverse2.getNext();
            }
            sum += up;
            if (sum > 9) {
                up = sum / 10;
            }
            tmpHead.setNext(new Node(sum % 10));
            tmpHead = tmpHead.getNext();
        }
        if (up > 0) {
            tmpHead.setNext(new Node(up));
        }

        tmpHead = reverseNodeList(newHead.getNext());

        return tmpHead;
    }
    private static Node reverseNodeList(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node curNext = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = curNext;
        }
        return pre;
    }