LeetCode刷题-----双指针

什么是双指针?双指针常常维护两个变量，left, right（或者slow,fast）来进行移动以解决一些常见的问题。

我把双指针技巧再分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组或者字符串中的问题，比如二分查找。
快慢指针:

左右指针:例如二分查找

了解了双指针以后，我们来看一下利用双指针解决的一些题目

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

Code:

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

Code:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if(head.next==null){
            return null;
        }
        ListNode L=new ListNode();
        L.next=head;
        ListNode slow=L,fast=L;
        for(;n>0;fast=fast.next,n--);
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        ListNode tmp=slow.next;
        slow.next=tmp.next;
        return L.next;
    }
}

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数
中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]
 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

 
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 

Code:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while(left<right){
            int num1=numbers[left];
            int num2=numbers[right];
            if(num1+num2<target)
                left++;
            else if(num1+num2>target)
                right--;
            else 
                break;
        }
        int nums[]={left+1,right+1};
        return nums;
    }
}

最后

以上就是勤奋大叔为你收集整理的LeetCode刷题-----双指针LeetCode刷题-----双指针的全部内容，希望文章能够帮你解决LeetCode刷题-----双指针LeetCode刷题-----双指针所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。