链表LinkedList

[TOC]

1、快慢指针

在数组章节我们学习的双指针技巧，通常是两个指针从前后一起遍历，向中间逼近；或者读写指针维护不同的数据元素；而在链表的运用中，由于单向链表只能单向遍历，通过调整两个指针的遍历速度完成某种特定任务，因此也称为”快慢指针“技巧。

快慢指针有几个常见的用法：

用法1：找单链表的中点

快指针走2步，慢指针走1步，当快指针走完的时候，慢指针刚好在一半的位置。

这类题目有：

• 143—重排链表，快慢的同时反转一部分链表

• 876—链表的中间节点

• 234—回文链表，快慢的同时反转一部分链表

用法2：判断是否相交，或者是否有环**

如果存在相交或者有环，那么两个指针一定会走到一起。

这类题目有 第 141 题，第 142 题，第 160 题。

• 141—判断链表是否有环

• 142—判断链表是否有环，如果有，返回环入口

• 160—相交链表，求两个链表的交点

用法3：寻找倒数第 N 个节点

快指针先行 N 步，慢指针再从头节点开始走，那么当快指针走到结束的时候，慢指针刚好走到第 N 个节点。

这类题目有：

• 19—删除链表中的倒数第N个节点

用法4：快慢指针形成一个窗口

对于要求链表中节点连续，并满足一定条件的题目，可使用 start/end 指针形成的窗口进行判断。

这类题目有：

• 82—删除链表中的重复元素2

• 817—链表的组件，类似求最长连续子序列和

2、哑结点

哑结点，也称为哨兵结点。常见的场景有：

用法1：保存结果集

遍历原链表，将最终的结果保存在哑结点起始的链表中。

这类题目有：

• 002—两数相加（开辟新空间保存结果）

• 021—合并两个有序链表（不需要开辟空间，直接将结果链接到哑结点上）