双指针

Ynthm Wang 收录于 Algorithm

2022-05-21 约 574 字预计阅读 2 分钟

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

同向双指针

快慢指针

在单向链表中找环

141 环形链表
142 环形链表 II

在单向链表中找环也是有多种办法，不过快慢双指针方法是其中最为简洁的方法之一。

首先两个指针都指向链表的头部，令一个指针一次走一步，另一个指针一次走两步，如果它们相遇了，证明有环，否则无环，时间复杂度 $O(n)$。

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


public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

如果有环的话，怎么找到环的起点呢？

设相遇时，慢指针一共走了 k 步，在环上走了 l 步（快慢指针在环上相遇时，慢指针一定没走完一圈）。快指针走了 2k 步，设环长为 C ，则有

$2k= n \times C - l + (k-l)$
$k = n \times C$

相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

 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


public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

相向双指针

判断字符串是否为回文字符串

1
2
3
4
5
6
7
8


 bool isPalindrome(string str)
 {
     int size = str.size();
     for (int i = 0, j = size - 1; i < size / 2; i++, j --)
         if (str[i] != str[j]) return false;
 ​
     return true;
 }

目录

双指针