今天的题目都是单项链表，单向链表的特点是只能单向遍历。主要的优化角度在于减少内存使用。

24. 两两交换链表中的节点 

用虚拟头结点，这样会方便很多。 

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。题目链接/文章讲解/视频讲解。

这个题写了两种解法，dummy_head直接写，理清楚顺序；第二个方法是递归，while内部的动作其实是重复的即递归思想，这样可以省却了while以及init的处理。

这个题再次体现了C++语法的精准性，每一个指针指向的元素是什么都非常的清晰，非常有利于把抽象问题具体化，很适合加深理解数据结构。

Python方法一：dummy_head暴力遍历：

试了两种写交换元素的方法，如果同时写，那么同时交换，不用写tmp元素；如果逐行写，需要想清楚先后顺序，并且创建中间tmp元素。第二种较为简洁。

Python方法二：递归

也可以用递归来写，相对比较简洁。不用处理init和while的细节，且需要交换的元素较少。

C++方法一：dummy_head暴力遍历：

记得清除缓存变量。

c++ 不像 python，go 那种能这样交换两个变量的值。逗号运算符它会忽略掉左边的表达式。所以这里没有Python的简洁版写法。只能利用中间变量逐步替换。

C++方法二：递归

19.删除链表的倒数第N个节点  

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。题目链接/文章讲解/视频讲解。

第一直觉是，遍历两遍，第一遍确定ListNode长度，第二遍删除第size-n个元素；遍历两遍提示我们可以用快慢指针来做，fast先走n步，再同时走slow fast直至最后一个node。细节上需要注意的是，考虑到n=1的情况，即删除最后一个元素，需要在倒数第二个元素时就决定，用dummy_head实现。

Python版本：

C++版本：

C++ 语法：

C++删除记得释放内存。

n--的用法是新学的。 C++：i++、++i、--i、i--、+=、-=、*=、/=你真的了解吗？

总是写错调用类属性的方式，head->next 而非head.next。

160. 链表相交  

本题没有视频讲解，大家注意 数值相同，不代表指针相同。题目链接/文章讲解。

这个题和19题类似用到了快慢指针，思考逻辑是：如果倒过来遍历，那么最长的相同的node就是答案。而单链表只能单个方向遍历，于是需要先统计出两个链表的长度，求出长度差，之后的步骤就和19题类似了，快慢指针。

Leetcode在LinkList输出无效值的时候，输出None，不能空白或者输出int(0)。

Python版本：

C++版本：

142.环形链表II  

算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。题目链接/文章讲解/视频讲解。

目前比较有意思的一个题，方法一是遍历，记录出现过的node，第二次出现的node即为入口，时间O(n)， 但是内存[1+2+3+...+n ~ n^2]。那么就开始考虑是否可以优化内存到O(n)，这个思路是经典的龟兔赛跑问题，用快慢指针的话一定会相遇，且图中x=z，在快指针只套了慢指针一圈的情况下，如果快指针比慢指针快了n圈（n>=2）的推导就比较妙了，x = （y+z）*k + z， 发现和n=1的情况是一样的，所以当快慢指针在met处相遇后，把慢指针放回head，那么下一次快慢指针相遇一定在x处。核心仍然是x=z。

Python方法一：暴力遍历

Python方法二：快慢指针

C++方法一：暴力遍历

C++关于集合的数据结构有set, unordered_set, map, unordered_map; unordered_set更接近Python中的set概念，但是这个题不能用unordered_set,因为集合内部元素是LinkList, unordered_set底层是hash_table, LinkList没有对应的hash函数，故不支持。所以适合map结构，map结构内部可以是LinkNode作为key。

C++方法二：快慢指针