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

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
        print(head1);
        print(inverseNode(head1));
	    //反转两个链表
        ListNode tmp1 = inverseNode(head1);
        ListNode tmp2 = inverseNode(head2);
        ListNode dummy = new ListNode(-1);
        int shang = 0;
	    // 反转后的两个链表从左往右依次移动指针
        while(tmp1 != null && tmp2 != null) {
		    // 1.求和、除以10，取商作为下一位的累加数，取余当做当前节点的数值
            int sum = tmp1.val + tmp2.val + shang;
            shang = sum / 10;
            int yushu = sum % 10;
            ListNode next = dummy.next;
		   // 2. new当前指针位置的节点并插入到头节点后面，同时插入后的节点的next指向原头节点的下一节点。同样也是头插法反转了链表，和前面的反转相互抵消就成正序的了
            dummy.next = new ListNode(yushu);
            dummy.next.next = next;
		   // 两个链表都向右移动一位
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        // 当前指针位置tmp1后面还有数，tmp2没有了
        while(tmp1 != null) {
            int sum = tmp1.val + shang;
            shang = sum / 10;
            int yushu = sum % 10;
            ListNode next = dummy.next;
            dummy.next = new ListNode(yushu);
            dummy.next.next = next;
            tmp1 = tmp1.next;
        }

        while(tmp2 != null) {
            int sum = tmp2.val + shang;
            shang = sum / 10;
            int yushu = sum % 10;
            ListNode next = dummy.next;
            dummy.next = new ListNode(yushu);
            dummy.next.next = next;
            tmp2 = tmp2.next;
        }
        // 最后还有进位时需要再添加该进位
        if(shang != 0) {
            ListNode next = dummy.next;
            dummy.next = new ListNode(shang);
            dummy.next.next = next;
        }
        return dummy.next;
    }
     // 通过头插法反转链表
    public ListNode inverseNode(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = head;
        ListNode cur = null;
       while(tmp != null) {
            ListNode next = dummy.next;
            dummy.next = new ListNode(tmp.val);
            dummy.next.next = next;
             
            tmp = tmp.next;
        }
        return dummy.next;
    }
    // 打印链表
    public void print(ListNode head) {
        ListNode tmp = head;
        while(tmp != null) {
            System.out.print(tmp.val + ",");
            tmp = tmp.next;
        }
        System.out.println();

    }





}