指针三剑客之一：链表

数据结构介绍

单向链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。LeetCode 默认的链表表示方法如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：

尽量处理当前节点的下一个节点而非当前节点本身。
建立一个虚拟节点 (Dummy Node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个 dummy 存在，返回 dummy->next 即可。

一般来说，算法题不需要删除内存。在刷 LeetCode 的时候，如果想要删除一个节点，可以直接进行指针操作而无需回收内存。实际做软件工程时，对于无用的内存，笔者建议尽量显式回收，或利用智能指针。

链表的基本操作

206. Reverse Linked List
链表翻转是非常基础也一定要掌握的技能。我们提供了两种写法——递归和非递归，建议你同时掌握这两种写法。

21. Merge Two Sorted Lists
我们提供了递归和非递归，共两种写法。

24. Swap Nodes in Pairs
利用指针进行交换操作，没有太大难度，但一定要细心。

其它链表技巧

160. Intersection of Two Linked Lists
我们使用两个指针，分别指向两个链表的头节点，并以相同的速度前进，若到达链表结尾，则移动到另一条链表的头节点继续前进。按照这种前进方法，两个指针会在 a + b + c 次前进后同时到达相交节点。

234. Palindrome Linked List
先使用快慢指针找到链表中点，再把链表切成两半；然后把后半段翻转；最后比较两半是否相等。

练习

83. Remove Duplicates from Sorted List
虽然 LeetCode 没有强制要求，但是我们仍然建议你回收内存，尤其当题目要求你删除的时候。

328. Odd Even Linked List
这道题其实很简单，千万不要把题目复杂化。

19. Remove Nth Node From End of List
既然我们可以使用快慢指针找到中点，也可以利用类似的方法找到倒数第 n 个节点，无需遍历第二遍。

148. Sort List
利用快慢指针找到链表中点后，可以对链表进行归并排序。