链表之和

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
        // write code here
        ListNode h1 = l1;
        ListNode h2 = l2;
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        int flag = 0;
        while (h1 != null || h2 != null) {
            int n1 = h1 == null ? 0 : h1.val;
            int n2 = h2 == null ? 0 : h2.val;
            
            flag = flag + n1 + n2;
            temp.next = new ListNode(flag % 10);
            flag /= 10;
            h1 = h1 == null ? null : h1.next;
            h2 = h2 == null ? null : h2.next;
            temp = temp.next;
        }
        if (flag != 0) {temp.next = new ListNode(flag);}
        return head.next;
    }
}

/**
有题目可以知道，数字在链表中是反向存储的，那么通过栈来时线逆序输出，从而可以得到一个数字
思路：
1）将两个给出的链表逆序输出从而转换成相应的数字
2）将两个数字相加，从而得到他们的和result
3）获得result的个位、十位（各个数位上的数字），然后插入在新建链表的链表头
4）返回新建的链表
将链表逆序输出：方法①通过栈来实现（由栈先进后出的特性），这个方法并没有改变原来的链表的顺序
方法②通过链表来实现，首先遍历原来的链表，然后将其节点查在新链表的尾节点处
*/
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
                //这里将链表对应的数字定义为long类型（因为刚开始提交的时候因为出现比int的范围更大的数，所以定义为long)
        long num1 = getNum(l1);
        long num2 = getNum(l2);//调用方法，从而获得链表对应的数字
        long result = num1 + num2;//获取和
        return getList(result);//获得和对应的链表,并将其返回
    }
    /**
    获得两个数的和对应的链表
    1）获得和对应的位数，并将其插入在链表尾
    */
    public ListNode getList(long sum){
        long temp;//表示位数
        ListNode list = new ListNode(0);
        if(sum == 0){//如果sum为0，那么就将返回值为0的链表
            return list;
        }
        //sum不为0
        while(sum != 0){
            temp = sum % 10;
            sum /= 10;
            ListNode node = new ListNode((int)temp);//新建节点
            //由于list是带假节点的链表，那么将从list开始遍历（无论是否链表为空，都可以，而不用判断链表是否为空）
            ListNode current = list;
            while(current.next != null){
                current = current.next;
            }
            node.next = current.next;
            current.next = node;
        }
        ListNode list2 = list.next;
        return list2;
    }
    /**
    获取链表中的有效节点数--通过遍历链表，从而得到
    */
    public int getCount(ListNode l){
        int count = 0;
        while(l != null){
            count++;
            l = l.next;
        }
        return count;
    }
    /**
    调用方法，从而获得对应的数字---通过栈来实现其倒序输出
    */
    public long getNum(ListNode l){
        int count = getCount(l);//获取链表的有效节点
        Stack stack = new Stack(count);//新建栈
        //遍历链表，从而将数字压栈
        while(l != null){
            stack.push(l.val);
            l = l.next;
        }
        //遍历栈，从而将获得链表对应的数字--当栈为空时，就退出循环遍历
        long result = 0;
        while(!stack.isEmpty()){
            result = result * 10 + stack.pop();
        }
        return result;
    }
}

class Stack{
    int[] arr;
    int top;//表示队头指针（栈的增删都靠队头指针实现）
    int maxSize;//栈的长度
    public Stack(int max){
        maxSize = max;
        arr = new int[maxSize];
        top = -1;//注意队头指针不能初始化尾0，因为数组的第一个下标就是0，不利于判断是否为空
    }
    //压栈
    public void push(int value){
        if(isFull()){
            //如果为满，就抛出异常，表明已经满了
            throw new RuntimeException("栈为满，无法插入");
        }
        arr[++top] = value;
    }
    //出栈
    public int pop(){
        if(isEmpty()){
            //如果为空，就抛出异常，表明为空
            throw new RuntimeException("栈为空，无法出栈");
        }
        return arr[top--];
    }
    //判断是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判断是否为满
    public boolean isFull(){
        return (top == maxSize - 1);
    }
}

 public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
                //这里将链表对应的数字定义为long类型（因为刚开始提交的时候因为出现比int的范围更大的数，所以定义为long)
        long num1 = getNum(l1);
        long num2 = getNum(l2);//调用方法，从而获得链表对应的数字
        long result = num1 + num2;//获取和
        return getList(result);//获得和对应的链表,并将其返回
    }

public ListNode add(ListNode head1 ,ListNode head2){ if(head1==null&&head2==null){ return null;
    } if(head1 ==null){ return head2;
    } if(head2==null){ return head1;
    } boolean flag = false; int i = 0; int real = 0;
//这里的val值随便指定 因为我们需要的是此cur的next结点作为我们生成的链表的头结点
    ListNode cur = new ListNode((head1.val+head2.val)%10);
//重新生成个cur的引用 后面我们返回这个ok.next就可以了（重新生成指针引用不修改原来指针）
    ListNode ok = cur; 
//如果两个链表都不是空 while (head1!=null&&head2!=null) { //通过flag判断是否进位  if (flag){
            i=1;
        }else {
            i=0;
        } int sum = head1.val+head2.val+i; if(sum<10){
             real = sum;
            flag = false;
        } if(sum>=10){
             real = sum%10;
            flag = true;
        }
        ListNode p = new ListNode(real);
        cur.next = p;
        cur = p;
        head1= head1.next;
        head2 = head2.next;
        } //如果1遍历到头但是2没到头  if(head1==null&&head2!=null){ int j = 0; while (head2!=null){ if(flag){
                    j = 1;
                }else {
                    j = 0;
                } int sum = head2.val+j; if(sum<10){
                    real = sum;
                    flag = false;
                } if(sum>=10){
                    real = sum%10;
                    flag = true;
                }
                ListNode p = new ListNode(real);
                cur.next = p;
                cur = p;
                head2 = head2.next;
            }
        }
 //如果2遍历到头但是1没到头


if(head1!=null&&head2==null){ int k = 0; while (head1!=null){ if(flag){
                k = 1;
            }else {
                k= 0;
            } int sum = head1.val+k; if(sum<10){
                real = sum;
                flag = false;
            } if(sum>=10){
                real = sum%10;
                flag = true;
            }
            ListNode p = new ListNode(real);
            cur.next = p;
            cur = p;
            head1 = head1.next;
        }
    } 

//最后都遍历后flag还是true  如果还是true说明仍然有进位 新生成结点值为1接在后面

System.out.println(flag); 

if(flag){
        ListNode p = new ListNode(1);
        cur.next = p;
        cur = p;
    } return ok.next;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        int sum = 0;
        int jinwei = 0;//用来做进位的,往右进位
        ListNode p = new ListNode(-1);
        ListNode head = p;
        while(l1 != null || l2 != null || jinwei != 0) {
            //l1和l2直接按位加起来
            if(l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!=null) {
                sum += l2.val;
                l2 = l2.next;
            }
            //再把进位加上
            sum += jinwei;
            p.next = new ListNode(sum%10);
            p = p.next;
            jinwei = sum / 10; //除以10用来下次循环进位
            sum = 0;   //清零等下次循环再相加       
        }
        return head.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int num1 = (l1 == null) ? 0 : l1.val;
            int num2 = (l2 == null) ? 0 : l2.val;
            int sum = num1 + num2 + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

• 增加一个整数carry就可以模拟数字相加了

public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
    // 先用堆栈存起来
    Stack<Integer> num1 = new Stack<>();
    Stack<Integer> num2 = new Stack<>();
    while (l1 != null) {
        num1.push(l1.val);
        l1 = l1.next;
    }

    while (l2 != null) {
        num2.push(l2.val);
        l2 = l2.next;
    }
    int carry = 0;    // 表示进位
    ListNode res = new ListNode(0);

    while (!num1.isEmpty() && !num2.isEmpty()) {
        ListNode tmp = new ListNode(num1.pop() + num2.pop() + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        tmp.next = res.next;
        res.next = tmp;
    }
    // 清掉num1
    while (!num1.isEmpty()) {
        ListNode tmp = new ListNode(num1.pop() + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        tmp.next = res.next;
        res.next = tmp;
    }

    // 清掉num2
    while (!num2.isEmpty()) {
        ListNode tmp = new ListNode(num2.pop() + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        tmp.next = res.next;
        res.next = tmp;
    }

    if (carry != 0) {
        ListNode tmp = new ListNode(carry);
        // 结果链表插入新节点
        tmp.next = res.next;
        res.next = tmp;
    }

    return res.next;
}

• 另外提供镜像题目的解，即链表和结果都是最高位在前的：Add Two Numbers II,思路就是借助stack来进行逆序操作

  public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
    // 结果链表
    ListNode res = new ListNode(0);    
    ListNode cur = res;    
    int carry = 0;    // 记录进位情况
    while (l1 != null && l2 != null) {
        ListNode tmp = new ListNode(l1.val + l2.val + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        cur.next = tmp;
        cur = cur.next;
        l1 = l1.next;
        l2 = l2.next;
    }
    // 清空num1
    while (l1 != null) {
        ListNode tmp = new ListNode(l1.val + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        cur.next = tmp;
        cur = cur.next;
        l1 = l1.next;
    }
  
    // 清空num2
    while (l2 != null) {
        ListNode tmp = new ListNode(l2.val + carry);
        if (tmp.val>=10) {
            carry = tmp.val / 10;
            tmp.val = tmp.val % 10;
        } else {
            carry = 0;
        }
        // 结果链表插入新节点
        cur.next = tmp;
        cur = cur.next;
        l2 = l2.next;
    }
  
    // 清掉carry
    if (carry != 0) {
        ListNode tmp = new ListNode(carry);
        // 结果链表插入新节点
        cur.next = tmp;
        cur = cur.next;
    }
  
    return res.next;
  }

  ​

参考代码：
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode head = new ListNode(0);
        ListNode p = head;
        int tmp = 0;
        while(l1!=null || l2!=null || tmp!=0){
            if(l1!=null){
                tmp += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                tmp += l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(tmp%10);
            p = p.next;
            tmp = tmp/10;
        }
        return head.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode res = new ListNode(0);
        ListNode tail = res;
        while(!(l1 == null && l2 == null && carry == 0)){
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            tail.next = newNode;
            tail = newNode;
            
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return res.next;
    }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {      //模拟加法算表
            sum /= 10;                          //保留进位
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);    //个位数字追加
            d = d.next;
        }
        if (sum / 10 == 1)                      //两个数相加，进位只可能是1
            d.next = new ListNode(1);
        return sentinel.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry=0;
        ListNode head=new ListNode(0);
        ListNode cur=head;
        while(l1!=null&&l2!=null){
        	cur.next=new ListNode((l1.val+l2.val+carry)%10);
            cur=cur.next;
            carry=(l1.val+l2.val+carry)/10;
            l1=l1.next;
            l2=l2.next;
        }
        while(l1!=null){
            cur.next=new ListNode((l1.val+carry)%10);
            cur=cur.next;
            carry=(l1.val+carry)/10;
            l1=l1.next;
        }
        while(l2!=null){
            cur.next=new ListNode((l2.val+carry)%10);
            cur=cur.next;
            carry=(l2.val+carry)/10;
            l2=l2.next;
        }
        if(carry!=0)
            cur.next=new ListNode(carry);
        return head.next;
    }
}

Two things to make the code simple:

1. Whenever one of the two ListNode is null, replace it with 0.
2. Keep the while loop going when at least one of the three conditions is met.

Let me know if there is something wrong. Thanks.

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode prev = new ListNode(0);
        ListNode head = prev;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            ListNode cur = new ListNode(0);
            int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
            cur.val = sum % 10; carry = sum / 10;
            prev.next = cur; prev = cur; l1 = (l1 == null) ? l1 : l1.next; l2 = (l2 == null) ? l2 : l2.next;
        }
        return head.next;
    }
}

import java.math.BigDecimal;
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		l2 = reverse(l2);
		l1 = reverse(l1);
		String s1 = "", s2 = "";
		while (l1 != null) {
			s1 += l1.val;
			l1 = l1.next;
		}
		while (l2 != null) {
			s2 += l2.val;
			l2 = l2.next;
		}
		String sum = new BigDecimal(s1).add(new BigDecimal(s2)).toString();
		ListNode dummy = new ListNode(0), p = dummy;
		for (int i = 0; i < sum.length(); i ++ ) {
			p.next = new ListNode(Integer.valueOf(sum.charAt(i) - '0'));
			p = p.next;
		}
		return reverse(dummy.next);
	}
	public static ListNode reverse(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode pre = head, cur = head.next, temp;
		head.next = null;
		while (cur != null) {
			temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		return pre;
	}
}