list node 节点大树算法

package ext.lc;

import java.util.HashSet;
import java.util.Set;

public class Solution {

    private static Set<ListNode> l = new HashSet<>();
    public static int[] vlist = new int[10];

    public static ListNode addTwoNumbers(ListNode n1, ListNode n2) {
        return addNext(n1, n2, null, null, 0);
    }

    public static ListNode addNext(ListNode n1, ListNode n2, ListNode p1,
                                   ListNode p2, int level) {
        if (n1 == null && n2 == null) {
            return null;
        } else if (n1 != null && n2 != null) {
            System.out.println("N1: " + n1.val + " N2:" + n2.val);
            if (n1.next != null || n2.next != null) {
                if (n1.next != null ^ n2.next != null) {
                    // At least one n.next is not null, recurse to find next
                    // 1,2,3 (next 3 is not null)
                    // 1,2,(2)(next is null, align to next
                    ListNode temp = addNext(n1.next == null ? n1 : n1.next,
                            n2.next == null ? n2 : n2.next, n1, n2, level + 1);
                    int val = temp.val;
                    temp.val = val % 10;
                    l.add(temp);
                    // 1,2,3
                    //   1,2(1 is p1/p2, whose next is null)
                    temp = new ListNode((n1.next == null ? p1.val : n1.val) + (n2.next == null ? p2.val : n2.val) + val / 10);
                    val = temp.val;
                    temp.val = val % 10;
                    // Update p for val > 9
                    if (p1 != null) {
                        p1.val += val / 10;
                    } else if (p2 != null) {
                        p2.val += val / 10;
                    }
                    // FIXME POS_1
                    if (n1.next == null) {
                        n1.val = p1.val;
                        n1.next = p1.next;
                    } else if (n2.next == null) {
                        n2.val = p2.val;
                        n2.next = p2.next;
                    }
                    vlist[level] = temp.val;
                    l.add(temp);
                    return temp;
                } else {
                    // all next are not null
                    ListNode temp = addNext(n1.next, n2.next, n1, n2,
                            level + 1);
                    l.add(temp);
                    // All next are not null, n is loop equals. n.next == n
                    // .next.net
                    // If so, n renew with p next for further check.
                    // Initialed by FIXME POS_1
                    renewNode(n1, p1);
                    renewNode(n2, p2);
                    int val = n1.val + n2.val;
                    temp = new ListNode(val % 10);
                    if (p1 != null) {
                        p1.val += val / 10;
                    } else if (p2 != null) {
                        p2.val += val / 10;
                    }
                    vlist[level] = temp.val;
                    l.add(temp);
                    return temp;
                }
            }
            // all next null, return n1 + n2
            int val = n1.val + n2.val;
            ListNode temp = new ListNode(val % 10);
            if (p1 != null) {
                p1.val += val / 10;
            } else if (p2 != null) {
                p2.val += val / 10;
            }
            vlist[level] = temp.val;
            l.add(temp);
            return temp;
        } else {
            // at least 1 null
            ListNode tNode = addNext(n1 == null ? null : n1.next, n2 == null ?
                    null : n2.next, n1, n2, level + 1);
            tNode = tNode == null ? (n1 == null ? n2 : n1) : tNode;
            vlist[level] = tNode.val;
            l.add(tNode);
            return tNode;
        }
    }

    /**
     * Check if n is loop equals n.next == n.next.next;
     * Renew n to p if p is not null.
     *
     * @param n
     * @param p
     */
    private static void renewNode(ListNode n, ListNode p) {
        if (n.next != null && n.next == n.next.next) {
            if (p == null) {
                n.val = 0;
            } else {
                n.val = p.val;
                n.next = p.next;
            }
        }
    }

    public static void main(String[] args) {
        // Init list1 7247
        ListNode n1 = new ListNode(7);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(4);
        ListNode n4 = new ListNode(7);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        // 7247
        //  954
        // 8201
        ListNode n11 = new ListNode(9);
        ListNode n12 = new ListNode(5);
        ListNode n13 = new ListNode(4);
        n11.next = n12;
        n12.next = n13;
        for (int i = 0; i < 10; i++) {
            System.out.print(vlist[i]);
        }
        System.out.println();
    }
}