数据结构复习

虽说是复习，但是都差不多忘干净了。而且用c做题做的多。
借从Leetcode上做题的机会，记一记自己之前学过的java知识。

链表

数组好歹写个动态规划，还能对六七十个样例，链表是一点头绪都没，尤其是要写头文件、写声明。

Lianbiao.1

• 逆序存储 顾名思义，一个数非要倒着给存到链表里。因为不熟悉链表，不知道链表的存取方式，想象不出来链表代码的实现方式，卡住。

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

敲了一遍第一个实现方法，感觉类似数组，要取模。
但是看了官方样例，修正数字 、next 等等 有梦比了。

抛开题目，Listnode, 顾名思义链表节点，在数据结构里是两个挨着的长方块，数据域data 和指针域next组成。

由题目知，两个非空的链表L1 L2
三元运算符 int n = 条件 ？真则执行： 假则执行
l1.val 指的是链表第一个值 l1.next表示下一个值

到这我就能看懂了，但是自己写不出来。不过够了。

Day02

简单题该会了吧

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

其实还是不会，但是我们来看一下结构。
首先对两个链表判空
如果都不为空，比较第一个值 val就是昨天的用法
从第一个结点来看，如果结点小，则把结点小的指针指下去

看了题解，意思是找列表的最小头节点，然后把头节点指向其他的结点。
因为两个链表是已经排序好的，所以每个链表的头节点必然是最小的，如果l1是小的，则把他指向下一个，如果l2 小，则讲l2指向更小的头节点。自己有点搞混了动态规划和递归了。做的题还是少。

做了两个改动
我把递归里边函数的两个参数交换了位置，还是能跑通。
还有弄明白了return的意思，return l1 的意思是返回他的值。

终于懂了，一个很简单的递归，以前学c++都是要自己写递归函数，java是直接给你这个递归函数，让你在他自身直接递归，边界条件是都为空，然后放心的把指针交出去指向他的子函数就完成了。其实，到现在我还是不懂.next的内部原理，不过做题就不影响了。