快慢指针的算法应用
2020-04-22 本文已影响0人
Arthurcsh
数据结构
快慢步长指针
环链表
上图中7是快慢指针相遇的节点,可以看出慢指针走了L+S步,快指针除了走L+S步外,还额外在环里绕了n圈,所以快指针走了L+S+nR步(R是环的长度),由于快指针的步长时慢指针的2倍,即2(L+S) = L+S+nR,即L+S = nR
快慢指针主要解决的问题:
- 寻找/删除第K个节点;
- 有关链表环问题解法:寻找/删除第K个节点。
问题一: 给定任意一个有序数组,计算出去重后的数组长度, 要求:只能在原数组中进行更改
去重数组长度// Objective-C
+ (int)removeDupllcates:(NSMutableArray*)nums {
if (nums.count==0) return 0;
int slow = 0;
for (int fast=0; fast<nums.count; fast++) {
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
}
NSLog(@"--- slow: %d, result: %@", slow, nums);
return slow+1;
}
+ (int)solutionDupllcates:(NSMutableArray*)nums {
int slow = 0, fast = 0;
while (true) {
fast++; // 快指针向右移动
// 快指针移动到数组末尾则退出,说明数组元素完成判断去重
if (fast >= nums.count) {
break;
}
if (nums[fast] == nums[slow]) {
continue; // 慢指针与快指针指向元素相同,说明重复元素;快指针继续向h右移动。
} else {
// 慢指针与快指针指向元素不同;则将快指针元素复制到慢指针后一位,这样b就保证慢指针后元素不重复
nums[slow+1] = nums[fast];
slow++; // 慢指针向右继续移动;
}
}
return slow + 1;
}
问题二: 给定一个带有头节点head的非空单链表,返回链表的中间节点,如果有两个中间节点,则返回第二个中间节点。
解法1: 哨兵法,如果哨兵节点中未定义长度,则需要遍历链表一次获取长度length,然后从头节点开始遍历length/2次,即可找到中间节点。
Node findMiddleNodeWithoutHead() {
Node tmp = head.next;
int length = 1;
// 遍历链表获取长度
While(tmp.next != null) {
tmp = tmp.next;
length++;
}
// 再遍历一次拿到链表中间节点
tmp = head.next;
Int middleLength = length/2;
While(middleLength > 0) {
tmp = tmp.next;
middleLength—;
}
return tmp;
}
解法2: 快慢指针,上面方法效率不高,需要经过两次遍历链表。
主要分三步:
1、快慢指针同时指向head的后继节点
2、慢指针走一步,快指针走两步;
3、不断重复步骤2
当链表长度为奇数时,fast.next = null,slow为中间节点
Node findMiddleNodeWithoutHead() {
Node slow = head.next;
Node fast = head.next;
While(fast != null && fast.next != null) {
// 快指针走2步
Fast = fast.next.next;
// 慢指针走1步
Slow = slow.next;
}
Return slow;
}
问题三:输入一个链表,输出该链表中倒数第K个节点。只用一次遍历时间复杂度O(n)
还是用快慢指针法:
1、首先让快慢指针同时指向head后继节点;
2、快指针往前走K-1步,使快慢指针相隔K个节点,会先走到K节点;
3、快慢指针同时往前走一步,不断重复此步骤,知道快指针走到尾节点,此时的slow节点即是要找的倒序第K个节点
快慢步长指针
Node findReverseTailNode(int k) {
Node slow = head.next;
Node fast = head.next;
// 快指针先到达第k节点
Int tmpK = k - 1;
While(tmpK > 0 && fast != null) {
Fast = fast.next;
tmpK—;
}
// 临界条件:k大于链表长度
If (fast == null) {
Return null;
}
// slow和fast同时前进,直到fast走到尾节点
While(fast.next != null) {
Slow = slow.next;
Fast = fast.next;
}
Return slow;
}
问题四:判断链表是否有环,如果有,找到环的入口位置,要求空间复杂度O(1)
环链表
/**
* 判断是否有环,返回快慢指针相遇节点,否则返回空指针
*/
Node detectCrossNode() {
Node slow = head;
Node fast = head;
// 如果fast为空或fast.next为空说明不是链表环
While(fast != null && fast.next != null) {
Fast = fast.next.next; // 快指针步长2
Slow = slow.next; // 慢指针步长1
if(fast == null) {
Return null;
}
If (fast == flow) {
Return flow;
}
}
Return null;
}
计算环链表
上图中7是快慢指针相遇的节点,可以看出慢指针走了L+S步,快指针除了走L+S步外,还额外在环里绕了n圈,所以快指针走了L+S+nR步(R是环的长度),由于快指针的步长时慢指针的2倍,即2(L+S) = L+S+nR,即L+S = nR
综上所述,要找到入口节点,只需要定义两个指针,一个指针指向head,另一个指针指向快慢指针相遇节点,然后这两个指针不断遍历,当它们指向同一个节点时即是环的入口节点。
Node getRingEntryNode() {
// 获取快慢指针相遇节点
Node crossNode = detectCrossNode();
// 如果没有相遇节点,则没有环
if(crossNode == null) {
Return null;
}
// 分别定义两个指针,一个指向head,一个指向相遇节点
Node slowNode = head;
Node fastNode = crossNode;
While(fastNode.next != slowNode.next) {
slowNode = slowNode.next;
fastNode = fastNode.next;
}
Return slowNode;
}