链表相加(二)

### 思路简单，清晰易懂

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode first = new ListNode(0);
        first.next = head1;
        ListNode second = new ListNode(0);
        second.next = head2;
        ListNode re = new ListNode(0);
        first = reverse(first);
        second = reverse(second);
        int index = 0;
        while(first!=null||second!=null){
            int x = first==null?0:first.val;
            int y = second==null?0:second.val;
            int sum = x+y+index;
            ListNode temp = new ListNode(sum%10);
            if(sum>=10){
                index = 1;
            }else{
                index=0;
            }
            temp.next = re.next;
            re.next = temp;
            if(first!=null)
            first=first.next;
            if(second!=null)
            second = second.next;
        }
        if(index==1){
            ListNode temp = new ListNode(1);
            temp.next = re.next;
            re.next = temp;
        }
        return re.next;
    }
    public ListNode reverse(ListNode head){
        ListNode point = head.next;
        head.next = null;
        while(point!=null){
            ListNode temp = point.next;
            point.next = head.next;
            head.next = point;
            point=temp;
        }
        return head.next;
    } 
}

public class Solution {     

    public ListNode addInList (ListNode head1, ListNode head2) {
        
        return toList(getNum(head1), getNum(head2));  //  调用自定义方法
    }

    public String getNum(ListNode head) {   // 链表 ==> String 数字
        StringBuilder num = new StringBuilder();
        while (head != null) {
            num.append(head.val);  // 使用String + 拼接会超时 !!!
            head = head.next;
        }
        return num.toString();
    }

    public ListNode toList(String s1, String s2) {  // String ==> 链表 (本质是NC1大数加法，可用BigInteger)
        ListNode head = null;
        int i = s1.length() - 1, j = s2.length() - 1, c = 0;
        while (i >= 0 || j >= 0 || c > 0) {   
            c += i >= 0 ? s1.charAt(i--) - '0' : 0;
            c += j >= 0 ? s2.charAt(j--) - '0' : 0;
            ListNode p = new ListNode(c % 10);
            p.next = head;
            head = p;
            c /= 10;
        }
        return head;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode sumNode = null;
        int carry = 0;
        ListNode new1=null, new2=null;
        while(head1!=null){
            ListNode flag = new ListNode(head1.val);
            flag.next = new1;
            new1 = flag;
            head1 = head1.next;
        }
        while(head2!=null){
            ListNode flag = new ListNode(head2.val);
            flag.next = new2;
            new2 = flag;
            head2 = head2.next;
        }
        while(new1!=null&&new2!=null){
            int flag = new1.val + new2.val + carry;
            ListNode newNode = new ListNode(flag%10);
            newNode.next = sumNode;
            sumNode = newNode;
            System.out.println(sumNode.val);
            if(flag>=10){
                carry = 1;
            }else{
                carry = 0;
            }
            new1 = new1.next;
            new2 = new2.next;
        }
        while(new1!=null){
            int flag = new1.val + carry;
            ListNode newNode = new ListNode(flag%10);
            newNode.next = sumNode;
            sumNode = newNode;
             if(flag>=10){
                carry = 1;
            }else{
                carry = 0;
            }
            new1 = new1.next;
        }
        while(new2!=null){
            int flag = new2.val + carry;
            ListNode newNode = new ListNode(flag%10);
            newNode.next = sumNode;
            sumNode = newNode;
             if(flag>=10){
                carry = 1;
            }else{
                carry = 0;
            }
            new2 = new2.next;
        }
        if(carry!=0){
            ListNode newNode = new ListNode(carry);
            newNode.next = sumNode;
            sumNode = newNode;
        }
        return sumNode;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        // 反转链表
        head1 = reverse(head1);
        head2 = reverse(head2);
        int ret = 0;
        while(head1 != null && head2 != null){
            int val = head1.val + head2.val + ret;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = cur.next;
            ret = val / 10;
            head1 = head1.next;
            head2 = head2.next;
        }
        while(head1 != null){
            int val = head1.val + ret;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = cur.next;
            ret = val / 10;
            head1 = head1.next;
        }
        while(head2 != null){
            int val = head2.val + ret;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = cur.next;
            ret = val / 10;
            head2 = head2.next;
        }
        while(ret != 0){
            ListNode node = new ListNode(ret % 10);
            cur.next = node;
            cur = cur.next;
            ret = ret / 10;
        }
        return reverse(dummy.next);
    }

    public ListNode reverse(ListNode head){
        if(head == null) return null;
        ListNode prev = head;
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        return reverseList(sumList(reverseList(head1), reverseList(head2)));
    }

    private ListNode reverseList(ListNode list) {
        if (list == null || list.next == null) {
            return list;
        }

        ListNode p = null;
        ListNode q = list;
        while (q != null) {
            ListNode r = q.next;
            q.next = p;
            p = q;
            q = r;
        }
        return p;
    }

    private ListNode sumList(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;

        ListNode p = list1;
        ListNode q = list2;
        int carry = 0;

        while (p != null || q != null) {
            int val = (p == null ? 0 : p.val) + (q == null ? 0 : q.val) + carry;

            carry = val / 10;
            val = val % 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            p = p == null ? p : p.next;
            q = q == null ? q : q.next;
        }
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.先把两个链表都遍历到底，统计各自结点个数，并得到个位指针
        // 此外，分别创建一个HashMap记录某个结点的上一个结点
        if (head1 == null || head1.val == 0) {
            return head2;
        }
        if (head2 == null || head2.val == 0) {
            return head1;
        }
        int length1 = 1;
        int length2 = 1;
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        HashMap<ListNode, ListNode> preNodeMap1 = new HashMap<>();
        HashMap<ListNode, ListNode> preNodeMap2 = new HashMap<>();
        // 预先把头结点及其前驱结点null存入HashMap
        preNodeMap1.put(head1, null);
        preNodeMap2.put(head2, null);
        while (cur1.next != null) {
            // cur1还不是最后一个结点
            length1++;
            // 存入结点cur1.next，及其前驱结点cur1
            preNodeMap1.put(cur1.next, cur1);
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            // cur2还不是最后一个结点
            length2++;
            // 存入结点cur2.next，及其前驱结点cur2
            preNodeMap2.put(cur2.next, cur2);
            cur2 = cur2.next;
        }
        // 此时，cur1和cur1指向了各自链表的最后一个非null结点

        // 2.两个链表同步往前遍历，直到各自的head
        ListNode result = null;
        int jinwei = 0;
        while (cur1 != null && cur2 != null) {
            // 3.创建result链表节点，对应结点相加，注意考虑进位，头插法
            int num1 = cur1.val;
            int num2 = cur2.val;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur1和cur2共同往前走一个结点
            cur1 = preNodeMap1.get(cur1);
            cur2 = preNodeMap2.get(cur2);
        }

        // 4.出了循环后，查看是否有一个链表没有走到头，让其无限加0即可
        // 以下两个while最多只会执行一个
        while (cur1 != null) {
            // 说明链表1没走到头，而链表2已经走到头了
            // 直接令num2 = 0
            int num1 = cur1.val;
            int num2 = 0;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur1往前走一个结点
            cur1 = preNodeMap1.get(cur1);
        }
        while (cur2 != null) {
            // 说明链表1已经走到头了，而链表2没走到头
            // 直接令num1 = 0
            int num1 = 0;
            int num2 = cur2.val;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur2往前走一个结点
            cur2 = preNodeMap2.get(cur2);
        }
        // 注意！此时jinwei中可能还有值！如果有的话，还需要再头插一个结点
        if (jinwei > 0) {
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(jinwei);
            curResultNode.next = result;
            result = curResultNode;
        }
        return result;
    }
}

//写的太差了
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        int n1 = 0;
        int n2 = 0;
        ListNode p1 = head1;
        ListNode p2 = head2;
        while(p1 != null){
            n1++;
            p1 = p1.next;
        }
        while(p2 != null){
            n2++;
            p2 = p2.next;
        }
        int[] num1 = new int[n1];
        int[] num2 = new int[n2];
        p1 = head1;
        p2 = head2;
        for(int i = 0;i<n1;i++){
            num1[i] = p1.val;
            p1 = p1.next;
        }
        for(int i = 0;i<n2;i++){
            num2[i] = p2.val;
            p2 = p2.next;
        }
        int flag = 0;
        int sumN = 0;
        if(n1 > n2){
            sumN = n1 + 1;
        }else{
            sumN = n2 + 1;
        }
        int[] res = new int[sumN];
        n1--;
        n2--;
        sumN--;
        while(n1 >= 0 && n2 >= 0){
            int temp = num1[n1] + num2[n2] + flag;
            if(temp > 9){
                flag = 1;
                res[sumN] = temp - 10;
            }else{
                flag = 0;
                res[sumN] = temp;
            }
            sumN--;
            n1--;
            n2--;
        }
        while(n1 >= 0){
            int temp = num1[n1] + flag;
            if(temp > 9){
                flag = 1;
                res[sumN] = temp - 10;
            }else{
                flag = 0;
                res[sumN] = temp;
            }
            sumN--;
            n1--;
        }
        while(n2 >= 0){
            int temp = num2[n2] + flag;
            if(temp > 9){
                flag = 1;
                res[sumN] = temp - 10;
            }else{
                flag = 0;
                res[sumN] = temp;
            }
            sumN--;
            n2--;
        }
        if(flag == 1){
            res[sumN] = 1;
        }else{
            res[sumN] = 0;
        }
        // for(int i = 0;i<res.length;i++)
        //     System.out.print(res[i]);
        
        ListNode resHead = new ListNode(0);
        ListNode p = resHead;
        for(int i = 0;i<res.length;i++){
            ListNode temp = new ListNode(res[i]);
            p.next = temp;
            p = p.next;
        }
        while(resHead.val == 0){
            resHead = resHead.next;
        }
        return resHead;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> stack3 = new Stack<>();
        while (head1 != null) {
            stack1.push(head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            stack2.push(head2.val);
            head2 = head2.next;
        }
        Integer flag = 0 ;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            Integer num1 = stack1.isEmpty() ? 0 : stack1.pop();
            Integer num2 = stack2.isEmpty() ? 0 : stack2.pop();
            Integer sum = num1 + num2 + flag;
            flag = sum >= 10 ? 1 : 0;
            stack3.push(sum % 10);
        }
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        while (!stack3.isEmpty()) {
            cur.next = new ListNode(stack3.pop());
            cur = cur.next;
        }
        if (flag == 1) {
            ListNode newHead = new ListNode(1);
            newHead.next = pre.next;
            return newHead;
        }
        return pre.next;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // store 2 lists to 2 Arraylists
        ArrayList<Integer> num1 = new ArrayList<>();
        ArrayList<Integer> num2 = new ArrayList<>();

        ListNode curr = head1;
        while (curr != null) {
            num1.add(curr.val);
            curr = curr.next;
        }

        curr = head2;
        while(curr != null) {
            num2.add(curr.val);
            curr = curr.next;
        }

        // reverse ArrayLists, make 2 ArrayLists the same size (0 padding)
        Collections.reverse(num1);
        Collections.reverse(num2);

        int maxSize = num1.size() > num2.size() ? num1.size() : num2.size();
        if (num1.size() < maxSize) {
            for (int i = num1.size(); i < maxSize; i++) {
                num1.add(0);
            }
        } else if (num2.size() < maxSize) {
            for (int i = num2.size(); i < maxSize; i++) {
                num2.add(0);
            }
        }
    
        // add operation
        ArrayList<Integer> sumReverse = new ArrayList<>();
        boolean hasCarry = false;
        for (int i = 0; i < maxSize; i++) {
            int sum = num1.get(i) + num2.get(i);
            sum += hasCarry ? 1 : 0;

            sumReverse.add(sum % 10);
            hasCarry = sum / 10 == 1 ? true : false;
        }
        if (hasCarry) { // last bit
            sumReverse.add(1);
        }

        // store the reverse ArrayList to list
        ListNode dummy = new ListNode(-1);
        curr = dummy;
        for (int i = sumReverse.size() - 1; i >=0; i--) {
            curr.next = new ListNode(sumReverse.get(i));
            curr = curr.next;
        }

        return dummy.next;
    }
}

public ListNode addInList1(ListNode head1, ListNode head2) {
        ArrayList<Integer> listNodes1 = new ArrayList<>();
        ArrayList<Integer> listNodes2 = new ArrayList<>();
        int n1 = 0;
        int n2 = 0;
        while (head1 != null) {
            n1++;
            listNodes1.add(head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            n2++;
            listNodes2.add(head2.val);
            head2 = head2.next;
        }
        int n = n1 > n2 ? n1 : n2;
        if (n1 < n) {
            for (int i = 0; i < n - n1; i++) {
                listNodes1.add(0);
            }
            for (int i = n - 1; i >= 0; i--) {
                if (i >= n - n1) {
                    listNodes1.set(i, listNodes1.get(i - (n - n1)));
                } else {
                    listNodes1.set(i, 0);
                }
            }
        } else if (n2 < n) {
            for (int i = 0; i < n - n2; i++) {
                listNodes2.add(0);
            }
            for (int i = n - 1; i >= 0; i--) {
                if (i >= n - n2) {
                    listNodes2.set(i, listNodes2.get(i - (n - n2)));
                } else {
                    listNodes2.set(i, 0);
                }
            }
        }
        ArrayList<ListNode> listNodes = new ArrayList<>();
        int jinwei = 0;
        for (int i = n - 1; i >= 0; i--) {
            int a = listNodes1.get(i) + listNodes2.get(i) + jinwei;
            if (a >= 10) {
                jinwei = 1;
                a = a - 10;
            } else {
                jinwei = 0;
            }
            listNodes.add(new ListNode(a));
        }
        if (jinwei == 1) {
            listNodes.add(new ListNode(1));
        }
        ListNode listNode = new ListNode(-1);
        for (int i = 0; i < listNodes.size(); i++) {
            ListNode pre = listNode;
            listNode = new ListNode(listNodes.get(i).val);
            listNode.next = i == 0 ? null : pre;
        }
        return listNode;
    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListInfo li1 = reverseList(head1);
        ListInfo li2 = reverseList(head2);
        ListNode p1 = li1.node;
        ListNode p2 = li2.node;
        int offset = 0;
        ListNode curr = null;
        ListNode dummyLong = li1.length > li2.length ? p1 : p2;
        ListNode dummyShort = li1.length > li2.length ? p2 : p1;
        ListNode dummyHead = dummyLong;
        //以长的链表为主体
        while (dummyLong != null) {
            int sum = (dummyShort == null ? 0 : dummyShort.val )
                      + dummyLong.val
                      + offset;
            //将计算结果覆盖原数值
            if (sum < 10) {
                dummyLong.val = sum;
                offset  = 0;
            } else {
                dummyLong.val = sum % 10;
                offset = sum / 10;
            }
            curr = dummyLong;
            if (dummyShort != null) {
                dummyShort = dummyShort.next;
            }
            dummyLong = dummyLong.next;
        }
        if (offset > 0) {
            //需要进位，创建新节点加到尾部
            ListNode top = new ListNode(offset);
            curr.next = top;
        }
        //链表再次反转，返回头节点
        head1 = reverseList(dummyHead).node;
        return  head1;
    }

    /**
     * 反转链表，返回链表信息（头节点、链表的长度）
     *
     *
     * @param head ListNode类
     * @return ListInfo类
     */
    public ListInfo reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        int length = 0;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nextTemp;
            length++;
        }
        return new ListInfo(pre, length);
    }

    class ListInfo {
        private ListNode node;
        private int length;

        ListInfo(ListNode node, int length) {
            this.node = node;
            this.length = length;
        }
    }

}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode p1 = head1;
        ListNode p2 = head2;
        ListNode c1 = head1;
        ListNode c2 = head2;
        Stack<Integer>s1 = new Stack<>();
        Stack<Integer>s2 = new Stack<>();
        Stack<Integer>res = new Stack<>();
        while (c1 != null) {
            s1.push(c1.val);
            c1 = c1.next;
        }
        while (c2 != null) {
            s2.push(c2.val);
            c2 = c2.next;
        }
        int carry = 0;
        while (!s1.isEmpty() || !s2.isEmpty()) {
            int sum = 0;
            if (!s1.isEmpty()) {
                sum += s1.pop();
            }
            if (!s2.isEmpty()) {
                sum += s2.pop();
            }
            sum += carry;
            carry = sum / 10;
            res.push(sum % 10);
        }
        ListNode node = new ListNode(-1);
        ListNode tail = node;
        while (!res.isEmpty()) {
            ListNode tmp = new ListNode(res.pop());
            tail.next = tmp;
            tmp.next = null;
            tail = tmp;
        }
        return node.next;
    }
}