数组和链表的区别：
https://zhuanlan.zhihu.com/p/52440208
存储方式导致查询、增加、删除复杂度不一样
数组连续缓存，查询快（o(1)），增加删除慢(o(1)~o(n))
链表分开存储，查询慢(o(1)~o(n))，增加删除快(o(1))
Leetcode160:. Intersection of Two Linked Lists
相交链表
解题思路1：求出两个链表的长度，做差，长的链表先把多余的部分读完，然后长短一起往下一个个读，并且每次对比，直到找到共同的，如果到末尾都没有就返回最后一个的next（也就是null）
找到一个类似思路，但是用时比我短（168ms,76.44%）,精简了下代码。
很明显，思路一太菜了，果断看答案
解题思路2：
第一个指针遍历A链表后指针指向B链表头部，第二个指针遍历B链表后指针指向A链表头部
图解：https://blog.csdn.net/qq_34364995/article/details/80518198
虽然思路二貌似时间更短，但是好像leetcode本身这个速度也不太稳定，第一遍提交的时候跟思路一速度差不多。
这题可拓展到有环的链表是否相交的问题，留个尾巴第二遍看吧。
Leetcode206：Reverse Linked List
反转链表
解题思路1：
很简单，遍历链表，用字典或数组把链表值记录下来，并求出链表长度，然后循环，挨个赋值给新的链表，被题解吐槽了，这个答案百分之二百会被问怎么优化（不用外部空间）。。。。
解题思路2：
也是循环，但是用了双指针，一个指针指前面一个，一个指针指当前位置，然后让当前指针的next指向前面一个，然后把两个指针都往后移一位，循环到最末位，就把整个链表倒过来了。这个思路真的快超级多。。。。。
解题思路3：
递归，也比较简单，head.next.next = head 详见题解。
Leetcode21: Merge Two Sorted Lists
合并两个有序链表
思路：递归
什么时候用递归：https://blog.csdn.net/iwordword/article/details/31417305
Leetcode83: Remove Duplicates from Sorted List
Leetcode19: Remove Nth Node From End of List **
删除链表倒数第N个节点
思路：
双指针循环，一个指针在前，一个指针指向它后面第n个元素，这里要注意考虑边界问题，比如[1,2] n = 2的情况，可以通过加一个哑节点在开头来避免。
Leetcode24:Swap Nodes in Pairs
两两交换链表中的节点
思路一:
递归，比较直接，但是递归的空间复杂度是 递归的深度（N）* 每次递归的复杂度，所以至少是O(n)
思路二：
迭代，得用三个指针才行，比较绕，但是空间复杂度O(1)
Leetcode445:Add Two Numbers II
两数相加
用两个栈，python用list实现即可（有pop）,先把两个链表都存在栈里，然后依次pop相加，注意考虑进位
Leetcode234:Palindrome Linked List
回文链表
思路一：
获得链表长度，找到中间点，把中间点后面的部分反转（方法参考反转链表），然后一个个比，如果都一样就返回True
时间复杂度：O(n) 空间复杂度：O(1)
思路二：
由于array的查找是O(1)复杂度，可以先把链表复制到array里，然后比较array从头往后读和从后往前读是否一样就可以了，array就用python里的list实现。这里有个索引的知识：
从后往前读一个list:
a[::-1]
(解释：a[i,j,s] 即 a[start,end,step] 当step为负数时是从后往前的意思，i和j缺省的话默认是从最后一位读到第一位）
时间复杂度：O(n) 空间复杂度：O(n)
思路三：
递归,时间复杂度：O(n) 空间复杂度：O(n),这个的官方题解有助于理解递归。
另附python公有私有讲解
Leetcode725:Split Linked List in Parts**
分隔链表
这题虽然是中等难度，但是思路比较直接，先算出链表长度为N,分k段，余数为r.则前r段长度为N//k+1, 后面的长度为N//k,迭代就行了
这两个思路的区别是用于输出到列表的链表是每次新建还是直接从当前链表取，思路二直接从当前链表取会快
Leetcode328:Odd Even Linked List**
奇偶链表
思路仍然比较直接，两个指针，一个指奇数位，一个指偶数位。但是代码实现过程有些细节需要考虑和优化。
思路（PS:Leetcode这个用时是在是方差太大了&&答案有个用三个指针的貌似还挺有意思的。）
以上，链表部分题目完毕。用的时间远远超出预计了。对链表算是了解了，还学了迭代、递归和双指针等，可喜可贺可喜可贺。
网友评论