前言
最近这两天在看牛客网上链表这块的算法题，一番苦战总结下来就是那些个套路，只要熟知一些常见的套路，碰见链表一类的算法题都会有个大概的思路。
全文包含的套路如下：
不过还有一些小细节就需要你自己在做题的过程中发现了，这里只是一些比较常见的套路，希望对你有所帮助。
快慢指针
快慢指针是指设置两个指针 slow 和 fast，前一个指针每次移动一步，而后一个指针每次移动两步。
其中移动步数的问题是不一定的，可以根据实际情况来决定
寻找链表的中间节点
快指针每次移动两步，而慢指针每次移动一步。
1
2
3
4
5
6
7
| ListNode fast = head;
ListNode slow = head;
while (slow.next != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = fast.next == null ? slow : slow.next;
|
寻找倒数第 K 个节点
快指针首先移动 K 步，随后与慢指针一起到达末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ListNode fast = pHead;
ListNode slow = pHead;
while (k-- < 0) {
if (fast == null) {
return null;
}
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
|
链表删除节点
删除当前节点
这个就没得说了，记录前一个节点即可。
1
2
3
4
5
6
7
| ListNode pre = slow;
while (fast != null) {
fast = fast.next;
pre = slow;
slow = slow.next;
}
pre.next = slow.next;
|
删除下一个节点
1
2
3
4
5
6
7
8
| ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
|
反转链表
输入一个链表，反转链表后，输出新链表的表头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode ret = null;
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
|
临时头节点
删除链表中重复出现的元素
通过设置一个 临时的头节点，这样在需要对头节点进行处理时会操作方便很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public ListNode deleteDuplicates (ListNode head) {
ListNode sign = new ListNode(1);
sign.next = head;
ListNode pre = sign;
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
ListNode tmp = cur.next;
while (tmp != null && cur.val == tmp.val) {
tmp = tmp.next;
}
pre.next = tmp;
cur = tmp;
} else {
pre = pre.next;
cur = cur.next;
}
}
return sign.next;
}
|
破坏当前节点
破坏当前节点 这种思路在判断链表是否存在环时非常的简便，同时空间复杂度 O(1)，但是缺点就是会 破坏链表的连续性。
如果题目要求不得破坏节点时，那么也可以使用 快慢指针 来判断是否存在环。
1
2
3
4
5
6
7
8
9
10
11
| public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
if (head.next == head) {
return true;
}
ListNode nextNode = head.next;
head.next = head;
return hasCycle(nextNode);
}
|
总结
1、 记住常见的套路并作为自己的知识消化。
2、 遇题不要慌，冷静分析，可以先在纸上画出基本的解题思路，然后再下手写代码不迟。
3、 check 通过，也不要高兴，而是应该多看看别人的解题思路跟你的区别，再想想自己的思路是否还有改进的机会。
4、 这里没有说明详细的算法流程，只是作者希望你在学会套路之后可以切身体会一下算法的奥妙。
5、 学海无涯苦作舟，算法无界等你闯。
个人备注
此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！