【LeetCode】《LeetCode 101》第十三章：链表

13.1 数据结构介绍

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

• LeetCode 默认的链表表示方式如下：

  struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(nullptr){}
  };
  

• 由于在进行链表操作的时候，尤其是删除节点，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：一是尽量处理当前节点的下一个节点而非当前节点；二是建立一个虚拟节点（dummy node），使其指向当前链表的头节点，这样即使原链表所有节点被删除，也会有一个 dummy 存在，返回 dummy->next 即可。

13.2 链表的基本操作

206. 反转链表（简单）

思路及代码： 206. 反转链表

21. 合并两个有序链表（简单）

思路及代码： 21. 合并两个有序链表

24.两两交换链表中的节点（中等）

思路及代码： 24.两两交换链表中的节点

13.3 其它链表技巧

160. 相交链表（简单）

思路及代码： 160. 相交链表

234. 回文链表（简单）

思路及代码： 234. 回文链表

13.4 练习

83. 删除排序链表中的重复元素（简单）

思路及代码： 83. 删除排序链表中的重复元素

328. 奇偶链表（中等）

思路及代码： 328. 奇偶链表

19. 删除链表的倒数第 N 个结点（中等）

思路及代码： 19. 删除链表的倒数第 N 个结点

148. 排序链表（中等）

思路及代码： 148. 排序链表

总结

• 指针题目通常需要画图，仔细分析节点之间的连接关系，确定连接顺序。

• 通常设置一个虚拟节点 dummy，注意书写方式。数据域可以不存储任何信息，指针域存储指向开始节点的指针（即第一个元素节点的存储位置）。 虚拟节点作用很大，可以自行百度。

  ListNode *dummy = new ListNode(), *cur = dummy;
  

• 链表的自定义构造函数（ACM模式需要自己写出来）：

  /*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
  

• 链表的其他技巧：通常用到数学思想，比如能够判断环的快慢指针，利用快慢指针找到链表中点。