双指针

Author: Bruce Yao Date: September 6, 2022 16:21:33 Category: 数据结构与算法

定义

双指针，通常指的是在遍历数组对象时，使用两个指针进行扫描。根据指针前进的方向不同分为快慢指针（方向相同）和对撞指针（方向相反）。双指针利用了数组索引有序的特征从而简化某些情况下的处理。

对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针，最右侧的索引定义为右指针，然后从两头向中间遍历。对撞指针适用于有序数组，可以考虑使用对撞指针来处理有序数组相关问题。
伪代码大致如下：

public void func(list) {
    int left = 0;
    int right = N - 1;
    
    while (left <= right) {
        left++;
        .....
        right--;
    }
}

快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，一般快指针移动 2，慢指针移动 1，当两个指针的值相等（或其他特殊条件）移动停止。
伪代码大致如下：

public void func(Node node) {
    Node slow = node;
    Node fast = node;
    
    while (slow.value != fast.value) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

快慢指针的应用

26 数组元素去重

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        // nums[i]和nums[j]不相等时，i指针才会向前移动，且a[i...j-1]的元素都是相等的
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

141 环形链表

public boolean hasCycle(ListNode head) {
    if (head == null && head.next == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (slow != fast) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

142 环形列表2

public ListNode func(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode index1 = slow;
            ListNode index2 = head;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }
    return null;
}

160 相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    ListNode Pa = headA;
    ListNode Pb = headB;
    
    while (Pa != Pb) {
        Pa = Pa == null ? headB : Pa.next;
        Pb = Pb == null ? headA : Pb.next;
    }
    
    return Pa;
}

链表二分

public ListNode EndOfFirstHalf(ListNode head) {
    
    ListNode slow = head;
    LsitNode fast = head;
    
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

参考

Tag(s):

back · home