数据结构算法之leetcode Add Two Numbers

两个非负整数的列表，每个元素都是一个数字，按照由低位到高位排序，求两个链表中的数相加并已链表的方式返回。

例如：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这里貌似没有什么高效算法，对两个链表同时遍历相加，并设置一个标识位用来表示是否需要进位。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = null;
        Stack<ListNode> stack = new Stack<ListNode>(); 
        int flag = 0;
        while(l1 != null && l2 != null){
            int sum = l1.val + l2.val + flag;
            int val = sum - 10;
            flag = 0;
            if(val >= 0){
                flag = 1;
            }else{
                val = sum;
            }
            ListNode nt = new ListNode(val);
            stack.push(nt);
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null){
            int sum = l1.val + flag;
            int val = sum - 10;
            flag = 0;
            if(val >= 0){
                flag = 1;
            }else{
                val = sum;
            }
            ListNode nt = new ListNode(val);
            stack.push(nt);
            l1 = l1.next;
        }
        while(l2 != null){
            int sum = l2.val + flag;
            int val = sum - 10;
            flag = 0;
            if(val >= 0){
                flag = 1;
            }else{
                val = sum;
            }
            ListNode nt = new ListNode(val);
            stack.push(nt);
            l2 = l2.next;
        }
        if(flag > 0){
            ListNode nt = new ListNode(1);
            stack.push(nt);
        }
        while(!stack.empty()){
            ListNode temp = null;
            temp = stack.pop();
            if(result == null){
                temp.next = null;
                result = temp;
            }else{
                temp.next = result;
                result = temp;
            }
            
        }
        return result;
    }
}

是不是很长，这里还用到了Stack，用Stack来存放各个链表中的各个ListNode。用Stack主要是为了把各个ListNode按照从后往前的顺序拼成链表。

链表的组建方式有两种，一种是从后往前建立连接，这样只需要一个指针；另一种是按照从前往后建立连接，此时需要两个指针，一个是指向链头的first指针，并且first在后续中不会发生变化，另一个指针是last，last会根据链表的元素向后移动，last始终指向链表的最后一个元素。

下面看下从链表头组建链表的代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode first = null;
        ListNode last = null;
        int flag = 0;
        while(l1 != null || l2 != null || flag != 0){
            int sum = flag;
            if(l1 != null){
                sum += l1.val;
            }
            if(l2 != null){
                sum += l2.val;
            }
            flag = sum / 10;
            int val = sum % 10;
            ListNode temp = new ListNode(val);
            if(first == null){
                first = temp;
            }
            if(last == null){
                last = temp;
            }else{
                last.next = temp;
                last = temp;
            }
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        return first;
    }
}

虽然这里多声明了一个变量指针，但是相较于第一个代码也算是一种优化，这里不需要额外的空间去存储相加之后的各个ListNode。时间复杂度都一样只是空间复杂度为O(1)

读上面代码链表组建中first和last指针的赋值是不是有一种一头雾水的感觉，得仔细读下才能撸明白，下面看下leetcode上面的解答代码，感觉比较清晰。代码如下：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

这里声明了一个val为0的dummyHead，使dummyHead作为链表的头节点，并声明一个移动指针curr也指向该节点，这样在链表创建的过程中不用进行太多的判断，只需移动指针curr即可(这也是链表的一种创建方法，貌似当初学数据结构时教科书就是用这种方法创建链表的)。