算法

快慢指针

Posted by Liao on 2020-03-18

快指针走两步，慢指针走一步，当它们相等时就是走了一个循环，为一个周期。

在链表中，如果一个链表存在环，那么快慢指针必然会相遇

LeetCode 快乐数

对于一个正整数，将这个数字替换为每个位置上的数字平方和，循环多次，如果能变为１则是快乐数，否则不是。

这道题用递归做的话，若正整数很大，递归层次深一点，就会导致调用栈爆了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getNext(int n){
        int sum = 0;
        while(n > 0){　　//用循环来处理正整数的每一位
            int a = n % 10;
            sum += a * a;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int fast = n,slow = n;
        do{
            slow = getNext(slow);
            fast = getNext(fast);
            fast = getNext(fast);
        }while(fast != slow);

        return slow == 1;
    }

LeetCode 各位相加

一样的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getNext(int n){
    int a;
    int sum = 0;
    while(n > 0){
        a = n % 10;
        sum += a;
        n /= 10;
    }
    return sum;
}
int addDigits(int n) {
    int fast = n,slow = n;
    do{
        fast = getNext(fast);
        fast = getNext(fast);
        slow = getNext(slow);
    }while(fast != slow);
    return slow;
}

通过慢指针将链表分为两部分：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。

LeetCode876. 链表的中间结点

1
2
3
4
5
6
7
8
ListNode* middleNode(ListNode* head) {
    ListNode* fast = head, *slow = head;
    while(fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
FEATURED TAGS
算法
FRIENDS