链表求和

题目描述

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
例子：给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null

思路

根据给出的链表头，以此向下访问链表中的每个节点，取出节点的val相加后创建新链表的节点，加入到新的链表里即可。
进位问题，考虑用一个list，如果val相加产生进位，则list加入1，否则加入0。每次val相加时读取list的最后一位即可。
思路很简单，但在链表操作的时候要小心！

代码

public class Solution {
	private ArrayList<Integer> aList;
	private ListNode ret;
	
	public ListNode addLists(ListNode l1, ListNode l2) {
		if(l1 == null) {
        	return l2;
        }else if(l2 == null){
			return l1;
		}else {
			aList = new ArrayList<>();
			ListNode res = new ListNode((l1.val + l2.val) % 10);
			ret = res;
			if((l1.val + l2.val) > 9) {
				aList.add(1);
			}else {
				aList.add(0);
			}
			
			l1 = l1.next;
			l2 = l2.next;
			
			while(l1 != null && l2 != null) {
				int val = l1.val + l2.val + aList.get(aList.size()-1);
				res.next = new ListNode(val % 10);
				res = res.next;
				l1 = l1.next;
				l2 = l2.next;
				if(val > 9) {
					aList.add(1);
	            }else {
					aList.add(0);
				}
			}
			
			// 收尾
			if(!(l1 == null)) {
				continueAdd(l1, aList, res);
			} else if (!(l2 == null)) {
				continueAdd(l2, aList, res);
			}else {
				if(aList.get(aList.size()-1) == 1) {
					res.next = new ListNode(1);
				}
			}
			return ret;
		}
    }
	
	private void continueAdd(ListNode listNode, ArrayList<Integer> list, ListNode res) {
		while(listNode != null) {
			int val = listNode.val + aList.get(aList.size()-1);
			if(val > 9) {
				aList.add(1);
            }else {
				aList.add(0);
			}
			res.next = new ListNode(val % 10);
			res = res.next;
			listNode = listNode.next;
		}
	}
	
	public ListNode initList(int[] num) {
		ListNode head = new ListNode(num[0]);
		ListNode ret = head;
		for(int i = 1; i < num.length; i++) {
			head.next = new ListNode(num[i]);
			head = head.next;
		}
		return ret;
	}

考差点

• 链表操作

不得不说，链表操作其实涉及到不少知识。
此算法中，我尝试按照给定的int[]数组构造链表，返回链表头。
首先，取出int[0]构造头部节点，之后创建next节点，直到读完所有数组。注意，这时不能让head对象立刻指向其next，因为这时head.next为null，一旦这么做了，那么头部节点将永远是null！正确的做法是，先new head.next，再让head = head.next
在java中，当使用 a = b （a、b均为JAVA对象）时，一定要慎重！
首先，你要保证，b对象已经new了！不然如果b=null，那么a=null，且不可逆（就算之后new了b）！为什么呢？

a = b的过程是：让a对象的栈指向b对象的堆！栈用来保存存储对象数据的堆地址。

下面假设几种情况：
b = c：如果在a的栈指向b的堆之前new过b了，那么b=c不会影响a，只是b的栈会指向c的堆，此时b和c共享c的堆，而a独享b的堆。所以一旦让对象a指向对象b，那么对象a将会一直盯着b的堆，只有b的堆中的数据改变了才会影响a。
a = b之前并未new b：这样会使得a并未真正指向一个堆，即a=null。就算之后new b，也只是b的栈指向了自己的堆（内存分配一块区域保存b对象的数据），但a的栈还是没有指向堆，a仍为null。