从C语言的指针开始，我的算法之路就结束了！

今天为了找个好的实习，不得不捡起来，写了三年的web，算法落下了太多了

今天在leetcode上刷题，难在了一个简单的链表上，因此记录一下

题目：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。　　　你可以假设除了数字 0 之外，这两个数字都不会以零开头。 示例：    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)    输出：7 -> 0 -> 8    原因：342 + 465 = 807

解题过程是几经波折的，最开始弄出来的答案还是头插式的，并且还超时了，真菜

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        int flag=0；//用于判断是否进位  1为进位，0为不进，可以直接做数值存储 　　　　 int sum=0;　//用于存放当前位相加的和        int i1=0;　 //l1的val        int i2=0;　 //l2的val        ListNode head=new ListNode(0);  //声明一个节点为头节点，因为是尾插，最终的node为最后一个节点的节点值        ListNode node=head;　　//声明一个临时变量，用于尾插的操作        while(l1!=null||l2!=null){
    　　　　　　　//如果当前节点为空，则赋值为0，方便继续运算            il = (l1 !=null) ? l1.val : 0;if(l2!=null){                i2=l2.val;            }else{                i2=0;            }                        sum=i1+i2+flag;  //得到当前运算的和            flag=sum/10;　　//是否进位 　　　　　　　//对当前节点尾插一个节点，存储当前节点的值  第一次运算时，相当于head.next=new ListNode(7)  这也是为什么最后返回head.next的原因            node.next=new ListNode(sum%10); 　　　　　　　//将当前节点的next赋值给当前节点，即将指针移到链表的尾部            node=node.next;            if (l1 != null) l1 = l1.next;            if (l2 != null) l2 = l2.next;        } 　　　　　//如果最后又进位，再给尾部插入一个新的节点        if (flag > 0) {            node.next = new ListNode(flag);        }        return head.next;    }}

在本题中，采用的是尾插法，不停的在链表的尾部插入新的节点

取值时，只需要对最开始的head进行向下取值即可

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807

0.开始循环之前

head={    val : 0    next : null}node={    val : 0    next : null}

1.第一次循环

node.next=new ListNode(sum%10); 运行结果：node={    val : 0    next : {        val : 7        next : null    }}由于head=node:head={    val : 0    next : {        val : 7        next : null    }}node=node.next;运行结果：node={    val : 7    next : null;}head不变

2.第二次循环

node.next=new ListNode(sum%10); 运行结果：node={    val : 7    next : {        val : 0        next : null    }}由于head=node:head={    val : 0    next : {        val : 7        next : {            val : 0            next : null        }    }}node=node.next;运行结果：node={    val : 0    next : null;}head不变

3.第三次循环

node.next=new ListNode(sum%10); 运行结果：node={    val : 0    next : {        val : 8        next : null    }}由于head=node:head={    val : 0    next : {        val : 7        next : {            val : 0            next : {                val : 8                next : null            }        }    }}node=node.next;运行结果：node={    val : 8    next : null;}head不变

4.返回结果

head={    val : 0    next : {        val : 7        next : {            val : 0            next : {                val : 8                next : null            }        }    }}head.next={    val : 7    next : {        val : 0        next : {            val : 8            next : null        }    }}

5.总结

最开始的head节点是整个运算中不动的，node节点相当于其的一个尾巴，不断的添加数据到自身，然后后移到添加的节点上去 类似于一个贪吃蛇，head节点一直不变，node节点是一个工作节点(长度为1) 　　他的工作是找到一个新的节点，让其附着在自己的next上（node.next=new ListNode） 　　然后移到到这个新的节点上去（node=node.next） 　　重复这项工作