0%

快慢指针.md

  • 141.链表是否有环 + 142.链表入环节点
    1. 快乐数
    1. 寻找重复数
    1. 删除链表的倒数第N个节点

链表是否有环 + 链表入环节点

链表是否有环 链表入环节点
快慢指针,快指针一次走两步,慢指针一次一步,若是两个指针相遇则有环 快慢指针,快指针一次走两步,慢指针一次一步,相遇后,慢指针回到head,这时两个指针都一次走一步,两个指针相遇处即为入环节点

第一次相遇时: fast走的步数是slow的2倍,即:f=2s fast比slow多走了n个环,假设环的长度是b,f=s+nb 因此有f=2nb, s=nb

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
leetcode 141

var hasCycle = function(head) {
if (head == null) return false;
if (head.next == null || head.next.next == null) return false;

var fast = head.next.next;
var slow = head;

while (fast.next !== null && fast.next.next !== null && slow.next !== null) {
if (fast == slow) return true;
fast = fast.next.next;
slow = slow.next;
}

return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
leetcode 142

var detectCycle = function(head) {
if (head == null || head.next == null) return null;

let slow = head;
let fast = head;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
};

if (fast == null || fast.next == null) return null;

slow = head;

while (slow != fast) {
slow = slow.next;
fast = fast.next;
}

return slow;
};

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False

我们计算happy number的过程中有可能出现重复的元素(无限循环),出现循环的时候判断是否为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var isHappy = function(n) {
let slow = n;
let fast = compute(n);

while (slow !== fast) {
slow = compute(slow);
fast = compute(fast);
fast = compute(fast);
}

return slow == 1;
};

var compute = function(n) {
let sum = 0;

while(n) {
const lastDigit = n % 10;
sum += (lastDigit * lastDigit);
n = Math.floor(n / 10);
}

return sum;
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

思路:快慢指针,每次跳转到对应的数的下标那里,如果有重复数,一定会出现环,现在就是找出环的入口,和环形链表二一样,只不过从链表的跳转变成了数组之间下标和数的跳转。以数组 [1,3,4,2,2],就会变成0->1->3->2->4->2->4->2->……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var findDuplicate = function(nums) {
var slow = 0;
var fast = 0;

slow = nums[slow];
fast = nums[nums[fast]];

while (slow !== fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}

var pre1 = 0;
var pre2 = slow;

while(pre1 !== pre2) {
pre1 = nums[pre1];
pre2 = nums[pre2];
}

return pre1;
};

19. 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第n个节点,并且返回链表的头结点。

思路:双指针,快指针先走n步,到达n处,此时慢指针出发和快指针一同前进,快指针到达尾部时,慢指针到达len-n处,位于倒数第n个节点处,删除这个节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var removeNthFromEnd = function(head, n) {
var pre = new ListNode(0);
pre.next = head;
var slow = pre;
var fast = pre;

for (var i = 0; i <= n; i++) {
fast = fast.next;
}

while (fast !== null) {
slow = slow.next;
fast = fast.next;
}

slow.next = slow.next.next;

return pre.next;
};