题解 | #链表相加(二)#

using System;
using System.Collections.Generic;

/*
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here

        //解题思路：利用栈存放所有结点，利用标记位存放是否两个结点之和大于10，利用头插法建立新结点


        //栈，存放第一个头指针以及后续所有元素
        var stack1 = new Stack<ListNode>();
        //栈，存放第二个头指针以及后续所有元素
        var stack2 = new Stack<ListNode>();

        // 标志，两数之和是否超过10
        bool overTen = false;
        //新建结点
        var node = new ListNode(-1);

        //head1中的所有结点入栈
        while (head1 != null) {
            stack1.Push(head1);
            head1 = head1.next;
        }
        //head2中的所有结点入栈
        while (head2 != null) {
            stack2.Push(head2);
            head2 = head2.next;
        }

        //若head1为空，直接返回head2
        if (stack1.Count == 0) return head2;
        //若head2为空，直接返回head1
        if (stack2.Count == 0) return head1;

        //两个栈都不为空，逐个元素相加
        while (stack1.Count > 0 && stack2.Count > 0) {
            //用overTen标记位判断当前结点之和是否要+1
            int count = overTen ? stack1.Pop().val + stack2.Pop().val + 1 : stack1.Pop().val
                        + stack2.Pop().val;

            //count<10 新建节点tmp，利用头插法插在node结点之后，并且将overTen设为false;
            if (count < 10) {
                var tmp = new ListNode(count);
                tmp.next = node.next;
                node.next = tmp;
                overTen = false;
            //count<10 新建节点tmp，利用头插法插在node结点之后，并且将overTen设为true;
            } else if (count >= 10) {
                var tmp = new ListNode(count % 10);
                tmp.next = node.next;
                node.next = tmp;
                overTen = true;
            }
        }
        //栈1不为空，判断上述最后一次两数之和是否大于10，并进行计算
        while (stack1.Count > 0) {
            int count = overTen ? stack1.Pop().val + 1 : stack1.Pop().val;
            if (count >= 10) {
                var tmp = new ListNode(count % 10);
                tmp.next = node.next;
                node.next = tmp;
                overTen = true;
            } else {
                overTen = false;
                var tmp = new ListNode(count);
                tmp.next = node.next;
                node.next = tmp;
                overTen = false;
            }
        }
        //栈2不为空，判断上述最后一次两数之和是否大于10，并进行计算
        while (stack2.Count > 0) {
            int count = overTen ? stack2.Pop().val + 1 : stack2.Pop().val;
            if (count >= 10) {
                var tmp = new ListNode(count % 10);
                tmp.next = node.next;
                node.next = tmp;
                overTen = true;
            } else {
                overTen = false;
                var tmp = new ListNode(count);
                tmp.next = node.next;
                node.next = tmp;
                overTen = false;
            }
        }

        //如果头结点的引用域的数值等于0，则上次发生了进位，新建节点1，利用头插法，插入到node之后
        if (node.next.val == 0) {
            var tmp = new ListNode(1);
            tmp.next = node.next;
            node.next = tmp;
        }
        return node.next;
    }
}