快慢指针能解决的相关问题

码农浅知-Java利用快慢指针解决中间值及链表相关问题

快慢指针解决中间值问题

1
2
3
4
5
6
7
8
9
10
11
public T getMid(Node first) {
    //定义快慢两个指针
    Node fast = first;
    Node slow = first;
    //使用两个指针遍历链表，快指针遍历完，慢指针所在的位置就是中间值
    while (fast != null && fast.next != null) {
        fast = fast.next.next;  //快指针步长一般设置为慢指针的2倍
        slow = slow.next;
    }
    return slow.item;
}

快慢指针解决链表是否有环问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isCircle(Node first) {
    //定义快慢两个指针
    Node fast = first;
    Node slow = first;
    //使用两个指针遍历链表，当快指针与慢指针重合时链表即有环
    while (fast != null && fast.next != null) {
        fast = fast.next.next;  //快指针步长一般设置为慢指针的2倍
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

快慢指针解决有环链表入口问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Node getEntrance(Node first) {
    //定义快慢两个指针和临时指针
    Node fast = first;
    Node slow = first;
    Node temp = null;
    //找环入口
    while (fast != null && fast.next != null) {
        fast = fast.next.next;  //快指针步长一般设置为慢指针的2倍
        slow = slow.next;
        if (fast == slow) {
            temp = first;   //当快慢指针相遇时，临时指针指向第一个结点
            continue;
        }
        if (temp != null) {
            temp = temp.next; //临时指针采用慢指针一样的步长
        }
        if (temp == slow) {
            break;  //当临时指针和慢指针相遇时，就找到了环的入口
        }
    }
    return temp;    //环的入口
}