链表相加(二)

//写的太差了
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;
    }
}

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) {  
        List<Integer> a = getNums(head1,head2);
        ListNode pre = null;
        ListNode p = null;
        for(int i = 0;i < a.size();i++){
          p = new ListNode(a.get(i));
          p.next = pre;
          pre = p;
        }  
        return p;
        
    }
    //将链表相加的结果放到List集合当中
    public ArrayList<Integer> getNums(ListNode node1,ListNode node2){
      ListNode node_1 = reverse(node1);
      ListNode node_2 = reverse(node2);
      ArrayList<Integer> a = new ArrayList<>();
      int add = 0;
      int b = 0;
      int c = 0;
      int sum = 0;
      while(node_1 != null || node_2 != null){
        if(node_1 == null){
          b = 0;
        }else{
          b = node_1.val;
          node_1 = node_1.next;
        }
        if(node_2 == null){
          c = 0;
        }else{
          c = node_2.val;
          node_2 = node_2.next;
        }
        sum = b+c+add;
        add = sum / 10;
        a.add(sum % 10);
      }
      if(add != 0){
        a.add(add);
      }
      return a;
    }
    //反转链表
    public ListNode reverse(ListNode node){
      ListNode sentry = new ListNode(0); 
      sentry.next = node;
      ListNode start = node;
      while(start.next != null){
        ListNode temp = start.next;
        start.next = temp.next;
        temp.next = sentry.next;
        sentry.next = temp;
      }
      return sentry.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) {

        if (head1 == null) return head2;
        if (head2 == null) return head1;

        // 反转链表，由于两个链表不能逆着遍历，又因为进行相加要低位对齐，所以先将两个表进行反转
        head1 = reverseListNode(head1);
        head2 = reverseListNode(head2);

        int up = 0; //记录进位
        int temp = 0; //记录相加后的存入链表中的值

        //先创建一个新链表的虚的头结点和一个cur节点
        ListNode dummp = new ListNode(-1);
        ListNode cur = dummp;

        //只要还有一个表为非空或者还有进位就需要继续循环
        while (head1 != null || head2 != null || up != 0) {

            //先判断一下链表的节点，如果是null，就赋值为0，否则就获得链表的节点的值
            int val1 = (head1 == null) ? 0 : head1.val;
            int val2 = (head2 == null) ? 0 : head2.val;

            temp = val1 + val2 + up; //相加结果
            up = temp / 10;   //进位
            temp = temp % 10;  //取余

            //新创建一个节点，存入相加取余10后的结果，存入新的节点中
            //将cur指向新的节点进行连接，并更新cur为下一个节点
            cur.next = new ListNode(temp);
            cur = cur.next;

            //如果当前的头结点为非空，就向后移动一个节点，否则就没有必要移动了，因为都是null,对应的值都为0
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }
        return reverseListNode(dummp.next);
    }

    /**
    * 反转链表
    * @param head
    * @return
    */
    private ListNode reverseListNode(ListNode head) {
        if (head == null) return null;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next; //断开链表，要记录后续一个
            cur.next = pre; //当前的next指向前一个
            pre = cur; //前一个更新为当前
            cur = temp; //当前更新为刚刚记录的后一个
        }
        return pre;
    }
}

public ListNode addInList (ListNode head1, ListNode head2) {
        Stack<Integer> st1=new Stack<>();
        Stack<Integer> st2=new Stack<>();
        while(head1!=null){
            st1.push(head1.val);
            head1=head1.next;
        }
        while(head2!=null){
            st2.push(head2.val);
            head2=head2.next;
        }
        int cur=0;
        ListNode ans=null;
        while(!st1.isEmpty()||!st2.isEmpty()||cur!=0){
            int tmp1=0;
            if(!st1.isEmpty()){
                tmp1=st1.pop();
            }else{
                tmp1=0;
            }
            int tmp2=0;
            if(!st2.isEmpty()){
                tmp2=st2.pop();
            }else{
                tmp2=0;
            }
            int carr=tmp1+tmp2+cur;
            cur=carr/10;
            carr=carr%10;//取余的结果
            ListNode tmppp=new ListNode(carr);
            tmppp.next=ans;
            ans=tmppp;
        }
        return ans;

    }

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 op1 = reverse(head1);
        ListNode op2 = reverse(head2);
        ListNode ans = add(op1,op2);
        return reverse(ans);
    }
    public ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode last = dummy.next;
        ListNode curr = last.next;//curr从第二个开始

        while (curr != null) {
            last.next = curr.next;
            curr.next = dummy.next;
            dummy.next = curr;
            curr = last.next;
        }
        return dummy.next;
    }
    public ListNode add(ListNode op1, ListNode op2) {
        int add1 = 0;
        int add2 = 0;
        int sum = 0;
        int cin = 0;
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while(op1 != null || op2 != null || cin != 0) {
            add1 = (op1 == null) ? 0 : op1.val;
            add2 = (op2 == null) ? 0 : op2.val;
            sum = (add1 + add2 + cin) % 10;
            cin = (add1 + add2 + cin) / 10;
            curr.next = new ListNode(sum);
            curr = curr.next;
            op1 = (op1 == null) ? null : op1.next;
            op2 = (op2 == null) ? null : op2.next;
        }
        return dummy.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) {
        ListNode l1 = reverse(head1), l2 = reverse(head2);
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;
        int t = 0;
        while (l1 != null || l2 != null) {
            int a = l1 != null ? l1.val : 0;
            int b = l2 != null ? l2.val : 0;
            t += a + b;
            tmp.next = new ListNode(t % 10);
            t /= 10;
            tmp = tmp.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (t > 0) tmp.next = new ListNode(t);
        return reverse(dummy.next);
    }
    public ListNode reverse(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public Stack<Integer> getNum(ListNode head, Stack<Integer> s) {//压入栈中
        ListNode cur = head;
        while (cur != null) {
            s.add(cur.val);
            cur = cur.next;
        }
        return s;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode vHead = new ListNode(-1);//虚头结点
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        s1 = getNum(head1, s1);//head1链表入栈
        s2 = getNum(head2, s2);//head2链表入栈
        int add = 0; //进位
        while (!(s1.isEmpty() || s2.isEmpty())) {
            int  result = 0;
            result = (s1.peek() + s2.peek() + add) % 10; //求值
            add = (s1.pop() + s2.pop() + add) / 10; //更新进位
            ListNode resultNode = new ListNode(result);

            ListNode temp = vHead.next;
            vHead.next = resultNode;
            resultNode.next = temp;
        }
        Stack<Integer> S = new Stack<Integer>();
        S = !s1.empty() ? s1 : s2;
    
        while (!S.empty()) {
            int result = (S.peek() + 0 + add) % 10;
            add = (S.pop() + 0 + add) / 10;
            ListNode resultNode = new ListNode(result);

            ListNode temp = vHead.next;
            vHead.next = resultNode;
            resultNode.next = temp;
        }
        if (add == 1) {//由于进位的关系,实际结果可能超过链表的长度
            ListNode resultNode = new ListNode(add);
            ListNode temp = vHead.next;
            vHead.next = resultNode;
            resultNode.next = temp;
        }

        return vHead.next;
    }
}