在许多数组和链表的题中,都需要用到双指针的思想来优化,本文总结归纳了几种常见的双指针和对应的应用案例,通过针对的性的刷题希望能熟练的掌握双指针的运用

167.两数之和II-输入有序数组(头尾指针)

在这里插入图片描述
定义两个指针,一个是头指针i,一个是尾指针j
判断 numbers[i]+numbers[j]与target的值大大小
如果相等,就返回下标+1的数组
如果target更大,说明数小了,i向后移
如果target更小,说明数大了,j向前移

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        int sum;
        while (i < j) {
            sum = numbers[i] + numbers[j];
            if (sum == target) return new int[]{i + 1, j + 1};
            else if (sum > target) j--;
            else i++;
        }
        return new int[0];
    }
}

633.平方数之和(头尾指针)

在这里插入图片描述
a和b的取值在0(int)Math.sqrt(c)之间
所以就以这两个值为上下界进行双指针遍历

public class Solution {
    public boolean judgeSquareSum(int c) {
        int i = 0;
        int j = (int) Math.sqrt(c);
        while (i <= j) {
            int tmp = i * i + j * j;
            if (tmp == c) return true;
            else if (tmp > c) j--;
            else i++;
        }
        return false;
    }
}

345.反转字符串中的元音字母(头尾指针)

在这里插入图片描述
题目的意思是将字符串的正数第n个元音字母倒数第n个元音字母交换
定义头指针i和尾指针j
定义一个char类型的数组
从头尾同时遍历,如果不是元音就直接加入新数组,如果是元音就等到两端都是元音了然后交换写入数组

public class Solution {
    public String reverseVowels(String s) {
        int i = 0;
        int j = s.length() - 1;
        char news[] = new char[s.length()];
        Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        while (i <= j) {
            char ci = s.charAt(i);
            char cj = s.charAt(j);
            if (!set.contains(ci)) news[i++] = ci;
            else if (!set.contains(cj)) news[j--] = cj;
            else {
                news[i++] = cj;
                news[j--] = ci;
            }
        }
        return new String(news);
    }
}

680.验证回文字符串Ⅱ(头尾指针)

在这里插入图片描述
定义头指针i和尾指针j
从头尾开始遍历,如果相等同时向中间缩进
如果发现不等,尝试删去i所在数和j所在数
删除后继续遍历,如果有任意一种情况能走完就符合回文字符串

public class Solution {
    public boolean validPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
            }
        }
        return true;
    }

    private boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
}

88.合并两个有序数组(异步指针)

在这里插入图片描述
从数组的尾部开始
定义一个指针k从新数组的最后一个位置开始
指针m,n分别从两个数组的最后一个数的位置开始
比较两个数组最后一个数的大小,大的放在新数字的指针处

如果有个数组指针为0了,判断是否是n的,如果是m就直接有序不需要处理,如果是n就依次填入新数组的位置

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[k--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        while (n >= 0) {
            nums1[k--] = nums2[n--];
        }
    }
}

21.合并两个有序链表(异步指针)

在这里插入图片描述
从头部开始
定义前驱指针pre
定义迭代的指针node = pre
判断连个指针l1和l2的值,把小的赋值给node.next
当迭代到有一个为空时,判断一下,把不为空的接在最后

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(-1);
        ListNode node = pre;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
                node = node.next;
            } else {
                node.next = l2;
                l2 = l2.next;
                node = node.next;
            }
        }
        if (l1 == null) node.next = l2;
        else node.next = l1;
        return pre.next;
    }
}

141.环形链表(快慢指针)

在这里插入图片描述
定义快指针fast和慢指针slow
fast一次走两步,slow一次走一步
关于为什么将fast设置为head.next:其实快慢指针中fast是head或者head.next都可以找到环,因为我们这里判断的是fast==slow,所以为了简化代码就保证他们初始就不一致,一旦一致就是有环

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;
    }
}

fast = head版本

public class Solution {
    public boolean hasCycle(ListNode head) {

        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

142.环形链表II(快慢指针)

在这里插入图片描述
在这里插入图片描述
思路:

  • 先和环形链表I一样判断有没有环,有才进行第二步
  • 从同一起点开始,fast一次走两步,slow一次走一步,当他们相遇之后,fast回到原点一次走一步,第二次相遇节点就是环连接点
  • 我的理解:
    • 假设第二圈发生第一次相遇,第二圈走完了就第二次相遇了
    • 第一次相遇时fast走了F+(a+b)+a
    • slow走了F+a
    • 因为fast是slow的两倍速度,所以第二次相遇时应该满足fast=2*slow
    • 设slow还需要走 x远第二次相遇,可得方程(F+2a+b+2x)=2(F+a+x),,解得F=b
    • 所以就假设fast以一倍的速度陪slow走完b,另一倍速从F出发,当fast与slow相遇时,相当于fast走过了b+F = 2b = 2倍slow的距离
    • 此时满足第二次相遇的情况
      public class Solution {
      public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;//找到第一次相遇
        }
        fast = head;//将fast移动到head
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }//第二次相遇
        return fast;
      }
      }

19.删除链表的倒数第N个节点(快慢指针)

在这里插入图片描述
本题也运用到了快慢指针,说明快慢指针在链表题中的地位

本题思路:

  • 移动快指针n步,使快慢指针步差为n
  • 如果此时快指针为null,说明要删除的节点是头结点,直接返回head.next;
  • 如果快指针不是null,那么就通过快慢指针查找到倒数第k+1个节点
  • 然后删除掉倒数第k个节点
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null || head.next == null) return null;

        ListNode fast = head;
        ListNode slow = head;

        //将fast和slow的步调差调成n,当fast到达末尾了,slow到达指定节点
        while (n-- > 0) {
            fast = fast.next;
        }
        //倒数的数就是头结点的情况,此时fast是null
        if (fast == null){
            return head.next;
        }

        //倒数的数不是头结点,按顺序移动fast和slow节点,直到倒数第二个,测试slow节点到达删除节点的上一个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //slow是待删除节点上一个节点,删除slow.next节点
        slow.next = slow.next.next;

        return head;

    }
}

234.回文链表(快慢指针)

在这里插入图片描述

O(n) 时间复杂度和 O(1) 空间复杂度解法:

  • 快慢指针找到中点
  • 将链表分割为两部分
  • 选择后一半进行翻转
  • 翻转后再次比较
public class Solution {
    /**
     * 快慢指针找到中点
     * 选择一半进行翻转
     * 翻转后再次比较
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;//偶数个结点,让slow指向下一个,作为后半段的开头

        //将链表分为以head和slow开头的等长的两段
        cut(head, slow);
        return isEqual(head, reverse(slow));
    }

    //翻转链表
    private ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }

    //判定两个链表是否相等
    private boolean isEqual(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null) {
            if (head1.val != head2.val) return false;
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }

    //分割链表
    private void cut(ListNode head, ListNode slow) {
        while (head.next != slow) {
            head = head.next;
        }
        head.next = null;
    }
}