leetcode算法讲解（LeetCode进阶-实战之快慢指针）
leetcode算法讲解（LeetCode进阶-实战之快慢指针）public ListNode removeNthFromEnd(ListNode head int n)参考代码出题人：阿里巴巴出题专家：屹平／阿里云视频云边缘计算高级技术专家参考答案我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n 1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。
闲聊
快慢指针的使用经常会出现在各大公司的面试题中，虽然出题形式千差万别但本质思想却殊途同归（看下文说明）。比如近期github开源的面试题项目，其中就有一道比较基础的题目考察对快慢指针的理解。在数据结构与算法的学习过程中学会举一反三很关键。
阿里面试题-给定一个链表，删除链表的倒数第N个节点，并且返回链表的头结点
示例： 给定一个链表: 1->2->3->4->5 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 要求： 只允许对链表进行一次遍历。
出题人：阿里巴巴出题专家：屹平／阿里云视频云边缘计算高级技术专家
参考答案
我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n 1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。
参考代码
public ListNode removeNthFromEnd(ListNode head int n)
{
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first
and second is n nodes apart
for (int i = 1; i <= n 1; i ) {
first = first.next;
}
// Move first to the end maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
复杂度分析
- 时间复杂度：O(L)，该算法对含有 L 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)。
- 空间复杂度：O(1)，我们只用了常量级的额外空间。
延伸
快慢指针类型的题目其实在leetcode上很常见，基本上有过快慢指针相关刷题经验的话在遇见本题的时候都能够秒解。随便从leetcode上摘一题作具体分析，比如876. Middle of the Linked List(链表的中间节点）
876. Middle of the Linked List
Given a non-empty singly linked list with head node head return a middle node of linked list.
If there are two middle nodes return the second middle node.
Example 1:
Input: [1 2 3 4 5]
Output: Node 3 from this list (Serialization: [3 4 5])
The returned node has value 3. (The judge's serialization of this node is [3 4 5]).
Note that we returned a ListNode object ans such that:
ans.val = 3 ans.next.val = 4 ans.next.next.val = 5 and ans.next.next.next = NULL.
Example 2:
Input: [1 2 3 4 5 6]
Output: Node 4 from this list (Serialization: [4 5 6])
Since the list has two middle nodes with values 3 and 4 we return the second one.
Note:
The number of nodes in the given list will be between 1 and 100.
876. 链表的中间结点
一个带有头结点head的非空单链表，返回链表的中间结点。
若该链表有两个中间结点，则返回第二个中间结点。
例1：
输入：[1 2 3 4 5]
输出：此列表中的结点为3 (序列化形式：[3 4 5])
返回的结点为3。 (检测系统序列化遍历该节点 [3 4 5])
注意，我们返回了的ListNode类型的数组ans，满足：
ans.val = 3 ans.next.val = 4 ans.next.next.val = 5 以及 ans.next.next.next = NULL.（意思是会最后会对结果middle以及其后的节点作校验）
例2：
输入：[1 2 3 4 5 6]
输出：此列表中的结点 4 (检测系统序列化遍历该节点：[4 5 6])
因为该列表有两个中间结点，值分别为3和4，最终返回第二个结点。
提示：
链表结点数介于1到100之间。
题意分析
本题属于典型的快慢指针查找题型，关于怎么确认链表相关的题型是否属于快慢指针题型，可以简单的根据题意判断：凡事需要查找的结果节点位置和链表位置相对位置明确，有属于链表节点查找问题，均可以条件反射般联想到快慢指针，就像早晨听见鸡打鸣就知道天快亮了一样。
思路设计
快慢指针思想，快指针和慢指针。每次循环的时候快指针后移两次，慢指针后移一次，达到边界时候停止循环，最终慢指针的位置必然为中间节点位置，因为移动次数快指针始终是慢指针的2倍。
伪代码
1、声明两个指针，慢指针和快指针；
2、while循环，循环条件为指针最终为null，即到达边界；
i.慢指针循环中每次移动一次；
ii.快指针循环中每次移动两次；
3、返回循环结束后的慢指针节点；
编码实践
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
复杂度分析
- 时间复杂度：O(n)，该算法对含有n个结点的列表进行了一次遍历 实际遍历次数为n/2。
- 空间复杂度：O(1)，我们只用了常量级的额外空间。
结语
对比阿里面试题以及leetcode876的题解分析可以验证出快慢指针的思路都是利用两个节点指针，在循环中同时移动快指针和慢指针，快指针与慢指针的位置根据需求设计，利用快指针在循环遍历过程中提前到达边界的这一特性，慢指针的最后到达位置即最终结果。通过对比进一步说明了要进国内大厂，数据结构与算法的重要性，刷leetcode的重要性！最后，如果觉得本文对你有所帮助或启发那就来个赞吧0.0～～
关注订阅号 获取更多干货～
