双指针★★★

解决哪类问题

:::success 分为左右指针、快慢指针
左右指针：数组问题或字符串问题，如查找子字符串
快慢指针：链表问题 :::

代码模板

左右指针

public int[] twoSum(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while(l < r) {
        if(nums[l] + nums[r] == target) {
            return new int[]{l + 1, r + 1};
        } else if(nums[l] + nums[r] < target) {
            l++;
        } else {
            r--;
        }
    }
    return new int[]{-1, -1};
}

快慢指针

public ListNode findMiddle(ListNode head) {
    // 初始化，让快指针和慢指针都处于链表的头部
    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.next != null) {
        // 如果快指针并且下一个不为空
        fast = fast.next.next; //快指针移动两个
        slow = slow.next; //慢指针移动一个
    }
    return slow;
}

public boolean hasCycle(ListNode head) {
    if (head == null)
        return false;
    // 快慢两个指针，初始时都指向链表的头结点
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        // 慢指针每次走一步
        slow = slow.next;
        // 快指针每次走两步
        fast = fast.next.next;
        //如果相遇，说明有环，直接返回true
        if (slow == fast)
            return true;
    }
    // 否则就是没环
    return false;
}

public ListNode removeBackEndNode(ListNode head, int n) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    // 初始时让快慢指针都指向链表的头部
    ListNode slow = dummyHead;
    ListNode fast = dummyHead;
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;  //为了解决断链问题
    return dummyHead.next;
}

public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null){
        return true;
    }
    ListNode pre = null; // 指向前一个节点的指针
    ListNode slow = head; // 慢指针
    ListNode fast = head; // 快指针
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        ListNode next = slow.next;
        slow.next = pre; // 修改慢指针走过的节点指向前一个节点
        pre = slow;
        slow = next;
    }
    if(fast != null){
        slow = slow.next;
        //当长度为奇数是，慢指针需要再走一个单位
    }
    while(pre!=null) {
        //判断是否为回文串
        if(pre.val != slow.val){
            return false;
        }
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}

复杂度

O(n)

运用思想

无

例题