19 | 重新认识数据结构（下）：有趣的“链表思维”

快乐数 leetcode 第 202 题 https://leetcode-cn.com/problems/happy-number/

思考题: 之前有见过这个链表成环的拓展题 一、 环的长度 思路: 从相遇节点开始，快慢指针继续走，直至相遇，走的次数就等于环的长度。很好理解，快指针是慢指针速度的一倍，就等价于一个慢指针走一个回路的距离，即是环的长度。 二、 求环的起点 思路:这个问题比较复杂点，不过画个图还是很好理解的。 假设: 起始点到入环点的距离为 D 相遇点到入环点的距离为 S1 环的长度为R 所以: 慢指针走的距离 D ＋ S1 快指针走的距离 D ＋ S1 + nR 又因为 快指针的速度 ＝ 两倍的慢指针的速度 方程为: 2(D ＋ S1) ＝ D ＋ S1 ＋ nR 得: D ＝ nR - S1 从这里可以得出结论，在第一次相遇时，D ＝ R - S1 有了这个结论，只要弄两个指针，一个设置为首节点，一个设置为首次相遇节点，然后每一次依次走一步，直至相遇，就是入环点了。 有了这个思路，代码实现起来，最多只是Debug的过程了。

1999999999 这个数字，按照各位平方和来进行计算，得到的下一个数字应该是 (9*9^2 + 1) = 730，也就是说，这个快乐数链表中，节点数量绝对不会超过 731 个 請問為什麼计算得到的下一个数字代表节点数量？

1999999999 这个数字，按照各位平方和来进行计算，得到的下一个数字应该是 (9*9^2 + 1) = 730，也就是说，这个快乐数链表中，节点数量绝对不会超过 731 个 请问老师，照这个思路，730以内各个数位平方和最大数应该是699，平方和是81+81+36=198，那么链表节点数是否应该在199=（1+198）个以内；198以内各个数位平方和最大的数是99，平方和是162，那么链表节点数最大应该在164=（2+162）以内，或者可以推出31位整型数据快乐数链表的最大长度是164，谢谢老师，学的有点晚了，不知您是否还浏览这个栏目。

int hasCycle(struct Node *head,int* rlong,int* begin) { if (head == NULL) return 0; // p 是慢指针，q 是快指针 struct Node * p = head, q = head; int np = 1,nq = 1; // 每次循环，p 走1步，q 走2步 do { p = p->next; q = q->next; np += 1; nq += 1; if (q == NULL) return 0; q = q->next; nq += 1; } while (p != q && q); *rlong = nq - np; struct Node * two=head; int rangbe = 0; do{ p = p->next; two = two->next; rangbe++; }while(p != two) *begin = rangbe; return 1; }

虽然是9次9的平方相乘加，9*9^2为什么不直接写成9^3呢？这样计算机程序不理解吗？可是它会算啊。让运动员跑圈用不用定义“距离”，就跑一圈，即使是环形也不会相遇。另外想问问胡老师这个null地址是最终目的吗？并且是定点指向一定要去往的地址吗？如果到不了null地址就知道有环。这需要定义最大值吗？不然如何停下呢？

示例代码中，p 和 q 应该是结构体指针类型而不是 int 类型吧

```go func isHappy(n int) bool { var nextNum = func (n int) int { next := 0 for n > 0 { t := n % 10 next += t * t n /= 10 } return next } p, q := n, n for { p, q = nextNum(p), nextNum(nextNum(q)) if p == q { break } } return q == 1 } ```

#include <stdio.h> #include <stdlib.h> typedef struct { int input; int output; } data_st_t;; data_st_t datas[800]; int calc(int in) { int out = 0; int digit; digit = in%10; while (in) { out += (in%10)*(in%10); in /=10; } return out; } int main() { int num = 0; int i; int val; printf("input num:"); fflush(stdout); scanf("%d", &num); if (num <= 0) { return -1; } while(1) { val = calc(num); printf("%d->%d\n", num, val); if (val == 1) { printf("happy num\n"); break; } if (datas[val].output) { printf("loop, unhappy\n"); break; } datas[val].input = num; datas[val].output = val; num = val; } return 0; }

找环起始点的方法：定义快慢指针为fast = head->next, slow = head. 然后让他们相遇。相遇后，头结点指针和慢指针同时移动，走到head = slow->next停下。此时head指向的就是环的起点。 这题可以用数学证明出来。假设链表非环部分的长度是x1, 环的长度是x2， slow的步长是d，fast的步长是2d，总共走了m步，那么在slow和fast相遇时，前者走了md= x1 + L, 后者走了m2d = x1 -1 + x2 + L, 因此我们有x1 + 1 = x2 - L,也就是说，head和slow要相遇的距离相差1,也就是head走到环起始点时，slow肯定相差一个步长，因此head = slow->next就是循环出口