概述
链表问题应该是数据结构中比较基础的一类问题，但同时也是在面试中常考的一类问题。但是围绕链表问题的一些基本方法或者处理思想，也无外乎那几类，因此本文尝试对链表常用的一些方法或者套路进行总结。
常用方法
1.头结点
增加 头结点或者说 哑巴节点这种方式，应该是我们在处理链表问题最常用的处理方式。简单来说引入头结点有两个优点：
- 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
- 无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非控表的处理也就统一了。
总而言之，通过增加头结点，减少了在链表处理过程中对边界情况的判断，大大简化了程序的编写。
下边我们看一个例子：
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个问题，可能解决问题的思路比较容易想：
由于链表的节点是有序的，因此我们可以在对链表进行遍历的过程中，可以比较当前遍历的节点(current)和其下一个节点（current.next）是否相等，如果相等则删除当前遍历的节点(current)，指针指向该节点的下一个节点，继续进行该操作。
具体代码如下所示:
public static ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
current = current.next;
while (current != null) {
while (current.next != null && current.val == current.next.val) {
current.next = current.next.next;
}
current = current.next;
}
return head;
}
整个解法应该比较容易理解，但此时我们考虑如果此处不使用头节点该如何解决该问题？
如果取消了头结点，我们就需要考虑对链表第一个节点的处理，因为在该问题上，链表的第一个节点也是有很大可能为重复节点，因此我们此处显然需要增加一个边界情况的判断，判断头结点是否为重复节点。(head.val == head.next.val)。并且需要针对其为头结点的情况单独进行处理。
因此，此处我们可以简单总结一下头结点方法的使用场景：
只要是要处理的链表 第一个节点本身会发生变化的情况都要考虑使用头结点，因为引入之后可能会极大的减少对边界清理的处理。
2. 链表排序
链表排序，本身也可以是一个算法的题目，同时也是我们在解决链表问题时常用的中间手段。
下边我们看一个题目：
148. 排序链表:
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
该问题明显就是一个链表问题，但其难点可能在于 对空间复杂度和时间复杂度的要求比较严苛。这就导致我们许多容易想到的方法都不能用，比如 插入排序、存储思想等。因此此处我们必须从复杂度为 O(nlogn)的排序算法中寻找到一个能用的，并且空间复杂度只有常数级别的算法。
首先考虑，时间复杂度小于等于O(nlog(n))的算法有：
- 折半插入排序
- 希尔排序
- 快速排序
- 堆排序
- 归并排序
- 基数排序
同时我们考虑到链表本身性能比较差，因此如果排序过程涉及大量的随机访问，大概率该算法不能用，比如快速排序、折半插入排序、希尔排序、堆排序（建堆的过程）。这些算法都不适用于链表。
基数排序空间复杂度比较大一般是 O（r），r是排序队列的个数。因此也不实用该题目。
最后我们只能考虑使用归并排序。
整个过程可以分成如下步骤：
- 拆分：找到链表中间节点，获取左半链表和右半链表
- 排序：分别对左侧链表和右侧链表进行归并排序
- 合并：将排序后的左侧链表和右侧链表进行合并
其过程可以简单用下图来表示：
代码实现如下：
// 使用归并算法进行链表排序
public static ListNode mergesort(ListNode head) {
// 如果链表只有一个节点直接返回
if (head == null || head.next == null) {
return head;
}
// 找到链表的中间节点
ListNode middle = findMiddle(head);
// 获取后半段的链表节点,同时与前半段节点断开
ListNode tail = middle.next;
middle.next = null;
// 对左侧进行排序
ListNode left = mergesort(head);
// 对右侧进行排序
ListNode right = mergesort(tail);
// 合并两条链,注意是将left和right进行合并
ListNode result = merge(left, right);
return result;
}
// 将两个有序链表进行合并
private static ListNode merge(ListNode left, ListNode right) {
ListNode headNode = new ListNode(0);
ListNode tail = headNode;
headNode.next = left;
while (left != null && right != null) {
if (left.val < right.val) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
// 将非空的节点直接链接到temp后边
if (left != null) {
tail.next = left;
}
if (right != null) {
tail.next = right;
}
return headNode.next;
}
// 寻找链表的中间节点，可以使用快慢指针
private static ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
// 快指针一次走两步
fast = fast.next.next;
// 慢指针一次走一步
slow = slow.next;
}
return slow;
}
3. 链表插入与删除
链表的插入与删除操作应该是解决链表问题最常用的基础手段。但关于链表的插入和删除还是有若干学问的，比如对链表进行插入，就可以简单分成 头插法和尾插法。链表删除也是有若干边界情况要考虑。但关于这两个操作是比较基础的，此处不进行详述，我们此处就看几个例题来回顾一下。
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个问题比较容易，此处直接给出一种思路，通过双指针来进行解决，一个指针指向当前遍历节点，另一个指针指向当前遍历节点的上一个节点，两个节点值一直，则删除当前遍历节点，以此类推。
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.next.val == current.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
4. 翻转链表
链表翻转应该是我们解决某些特殊问题的时候，比较有效的突破口，尤其是那些对链表按照指定规则进行重排序的问题，在无计可施的时候，通过翻转有时候可以有效的找到突破口。
143.重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
通过链表翻转，我们可以迅速想到一种 思路：
找到中点断开，翻转后面部分，然后合并前后两个链表
具体代码实现如下：
/** 按照要求重新对链表进行排序: 给定链表 1->2->3->4, 重新排列为 1->4->2->3. */
public static void reorderList(ListNode head) {
// 边界情况进行处理，如果只有一个节点或者节点为空，直接返回
if (head == null || head.next == null) {
return;
}
// 如果只有一个节点直接反掌结果
if (head == null || head.next == null) {
return;
}
ListNode headNode = new ListNode(0);
headNode.next = head;
// 获取中间链表节点
ListNode middle = getMiddle(head);
ListNode tail = middle.next;
middle.next = null;
// 对后一半的链表进行翻转
tail = reverse(tail);
ListNode temp = headNode;
// 将两段链表交替连接
while (head != null && tail != null) {
temp.next = head;
head = head.next;
temp = temp.next;
temp.next = tail;
tail = tail.next;
temp = temp.next;
}
// 非空节点连接到链表末尾
if (head != null) {
temp.next = head;
}
if (tail != null) {
temp.next = tail;
}
}
// 对链表进行翻转
private static ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode temp;
while (head != null) {
temp = head.next;
// 此处应该通过head的next来实现翻转
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
// 获取链表的中间节点
private static ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
当然解决该问题的方法不知一种，比如我们也可以用存储的思路的来解决，将链表转成ArrayList来进行解决。具体代码如下：
/**
* 使用存储解决该问题
* 基本思路：将链表转换乘ArraryList类型然后从后向前来进行遍历
* @param head
*/
public static void reorderListByStorage(ListNode head) {
//边界情况处理
if(head == null || head.next == null){
return;
}
//将链表转换乘ArrayList进行操作
ArrayList list = new ArrayList();
while (head != null){
list.add(head);
head = head.next;
}
//通过双指针连接乘新的链表
int i=0,j=list.size()-1;
while (i
5. 快慢指针
快慢指针或者说双指针，毫无疑问是解决链表问题最常用的操作，比如在寻找链表中间节点的时候就很常用。
private static ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
而且应用起来也比较灵活，比如可以用来判断链表是否有环：
141. 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1
代码如下：
/**
* 使用快慢指针来解决链表是否有环的判断
* @param head
* @return
*/
public static boolean hasCycle(ListNode head){
//边界情况处理
if (head ==null || head.next ==null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
boolean hasCycle = false;
while (fast != null && fast.next != null){
//如果两个指针重逢则证明一定有环
if (fast == slow){
hasCycle = true;
break;
}
//slow指针每次走一步，fast指针每次走两步
slow = slow.next;
fast = fast.next.next;
}
return hasCycle;
}
总结
本文主要总结了解决链表问题时，常用的一些套路，比如增加头结点、对链表进行排序、节点插入与删除、链表翻转以及快慢指针，希望能给读者以帮助。
Original: https://www.cnblogs.com/goWithHappy/p/some-methods-of-linklist.html
Author: vcjmhg
Title: 链表问题一些常用的套路与方法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/599497/
转载文章受原作者版权保护。转载请注明原作者出处！