1. 环形链表判断方法-快慢指针

LeetCode 141

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* fast = head, * slow = head;
        if (head == NULL || head->next == NULL) return false;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

总结：判断链表是否有环，可以用一个快指针一个慢指针移动的原理看看二者是否会相遇，相遇则有环

​

2. 快乐数的巧解-抽象成链式关系

LeetCode 202

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	int getNext(int num) {
		int rst = 0;
		while (num != 0) {
			int sofar = num % 10;
			num /= 10;
			rst += sofar*sofar;
		}
		return rst;
	}

	bool isHappy(int n) {
		int fast = n, slow = n;
		while ( fast != 1 ) {
			fast = getNext(getNext(fast));
			slow = getNext(slow);
			if (fast == slow && slow != 1) return false;
		}
		return true;
	}
};

总结：一个数可以有下一个数对应，则有链式关系，其中无限循环可以用环形链表判断来搞定，这样就形成了巧解