Java雙指針法怎么使用

本文小編為大家詳細(xì)介紹“Java雙指針法怎么使用”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Java雙指針法怎么使用”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

前言

通常用在線性的數(shù)據(jù)結(jié)構(gòu)中，比如鏈表和數(shù)組。

指針其實(shí)就是數(shù)據(jù)的索引或者鏈表的結(jié)點(diǎn)。兩個(gè)指針朝著左右兩個(gè)方向移動，直到滿足搜索條件。 雙指針可分為同向雙指針、異向雙指針、快慢指針、滑動窗口。根據(jù)需求選擇雙指針的模型，比如 刪除數(shù)組或鏈表中重復(fù)的元素，同向雙指針（線性表前提是有序的）； 快慢指針一般用在鏈表中，比如求鏈表的中點(diǎn)、判斷鏈表是否有環(huán)、判斷鏈表換的起點(diǎn)、環(huán)的長度、以及鏈表的倒數(shù)第K個(gè)元素； 比如在二分查找中用的就是異向雙指針； 滑動窗口其實(shí)就是在數(shù)組或者鏈表某個(gè)區(qū)間上的操作，比如求最長/最短子字符串或是特定子字符串的長度要求。

1.判斷鏈表是否有環(huán)

力扣141題

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識鏈表的實(shí)際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

代碼實(shí)現(xiàn)

public class Solution {
    //快慢指針法
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            //此時(shí)相遇了
            if(fast == low){
                return true;
            }
        }
        return false;
    }
}

2.查找鏈表中間的元素

力扣876題

給定一個(gè)頭結(jié)點(diǎn)為 head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

代碼實(shí)現(xiàn)

  //快慢指針法
    public ListNode middleNode(ListNode head) {
        ListNode low = head,fast = head;
        while(fast != null && fast.next != null){
            //慢指針走一步
            low = low.next;
            //快指針走兩步
            fast = fast.next.next;
        }
        //奇數(shù)，fast.next = null時(shí)，low即為所求
        //偶數(shù)，fsat == null時(shí)，low即為所求
        return low;
    }

3.奇偶排序前奇后偶

力扣328題

給定單鏈表的頭節(jié)點(diǎn) head ，將所有索引為奇數(shù)的節(jié)點(diǎn)和索引為偶數(shù)的節(jié)點(diǎn)分別組合在一起，然后返回重新排序的列表。

第一個(gè)節(jié)點(diǎn)的索引被認(rèn)為是 奇數(shù) ， 第二個(gè)節(jié)點(diǎn)的索引為 偶數(shù) ，以此類推。

代碼實(shí)現(xiàn)

 public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fastHead = head.next;
        ListNode lowTail = head;//奇數(shù)鏈表
        ListNode fastTail = fastHead;//偶數(shù)鏈表
        while(fastTail != null && fastTail.next != null){
            //更新奇數(shù)節(jié)點(diǎn)時(shí)，奇數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)需要指向偶數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            lowTail.next = fastTail.next;
            lowTail = lowTail.next;
           // 更新偶數(shù)節(jié)點(diǎn)時(shí)，偶數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)需要指向奇數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            fastTail.next = lowTail.next;
            fastTail = fastTail.next;
        }
        //合并兩個(gè)鏈表
        lowTail.next = fastHead;
        return head;
    }

4.刪除排序鏈表的重復(fù)元素

力扣82題

給定一個(gè)已排序的鏈表的頭 head ， 刪除原始鏈表中所有重復(fù)數(shù)字的節(jié)點(diǎn)，只留下不同的數(shù)字 。返回 已排序的鏈表

代碼實(shí)現(xiàn)

 public ListNode deleteDuplicates(ListNode head) {
        //虛擬頭節(jié)點(diǎn)法
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while(cur != null){
            //引入next指針
            ListNode next = cur.next;
            if(next == null){
                //只有一個(gè)元素
                return dummyHead.next;
            }
            if(cur.val != next.val){
                //cur不是重復(fù)節(jié)點(diǎn)，三指針都移動
                cur = cur.next;
                prev = prev.next;
            }else{
                //讓next指針一直向后移動，直到與cur.val不相等的節(jié)點(diǎn)位置
                while(next != null && cur.val == next.val){
                    next = next.next;
                }
                // 此時(shí)next指向了第一個(gè)不重復(fù)的元素
                // 此時(shí)prev - next之間所有重復(fù)元素全部刪除
                prev.next = next;
                cur = next;
            }
        }
        return dummyHead.next;
    }

5.三數(shù)之和

力扣15題

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

代碼實(shí)現(xiàn)

 public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚舉 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚舉的數(shù)不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 對應(yīng)的指針初始指向數(shù)組的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚舉 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚舉的數(shù)不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保證 b 的指針在 c 的指針的左側(cè)
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指針重合，隨著 b 后續(xù)的增加
                // 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

6.分割鏈表

力扣面試題02.04

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x ，請你對鏈表進(jìn)行分隔，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前。

你不需要 保留 每個(gè)分區(qū)中各節(jié)點(diǎn)的初始相對位置。

代碼實(shí)現(xiàn)

 public ListNode partition(ListNode head, int x) {
        // 創(chuàng)建small和big兩個(gè)小鏈表的頭節(jié)點(diǎn)
        ListNode smallHead = new ListNode(-1);
        ListNode bigHead = new ListNode(-1);
        // 按照升序插入，因此需要尾插
        // 分別指向兩個(gè)子鏈表的尾部
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;
        //遍歷原鏈表，根據(jù)值放入small和big鏈表中
        while(head != null){
            if(head.val < x){
                smallTail.next = head;
                smallTail = head;
            }else{
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        bigTail.next = null;
        //拼接小鏈表和大鏈表
        smallTail.next = bigHead.next;
        return smallHead.next;
    }

7.合并兩個(gè)有序的數(shù)組

力扣88題

給你兩個(gè)按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個(gè)整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素?cái)?shù)目。請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況，nums1 的初始長度為 m + n，其中前 m 個(gè)元素表示應(yīng)合并的元素，后 n 個(gè)元素為 0 ，應(yīng)忽略。nums2 的長度為 n 。

代碼實(shí)現(xiàn)

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }

8.兩數(shù)之和—輸入有序數(shù)組

力扣167題

給你一個(gè)下標(biāo)從 1 開始的整數(shù)數(shù)組 numbers ，該數(shù)組已按 非遞減順序排列 ，請你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù) target 的兩個(gè)數(shù)。如果設(shè)這兩個(gè)數(shù)分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數(shù)數(shù)組 [index1, index2] 的形式返回這兩個(gè)整數(shù)的下標(biāo) index1 和 index2。

代碼實(shí)現(xiàn)

 public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }

9.長度最小的子數(shù)組

（力扣209）給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足其和 &ge; target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, &hellip;, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0

代碼實(shí)現(xiàn)

//滑動窗口法
 public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

10.排序鏈表

給你鏈表的頭結(jié)點(diǎn) head ，請將其按 升序 排列并返回 排序后的鏈表 。

解題思路

通過遞歸實(shí)現(xiàn)鏈表歸并排序，有以下兩個(gè)環(huán)節(jié)：

1，分割 cut 環(huán)節(jié)： 找到當(dāng)前鏈表中點(diǎn)，并從中點(diǎn)將鏈表斷開（以便在下次遞歸 cut 時(shí)，鏈表片段擁有正確邊界）； 我們使用 fast,slow 快慢雙指針法，奇數(shù)個(gè)節(jié)點(diǎn)找到中點(diǎn)，偶數(shù)個(gè)節(jié)點(diǎn)找到中心左邊的節(jié)點(diǎn)。 找到中點(diǎn) slow 后，執(zhí)行 slow.next = None 將鏈表切斷。 遞歸分割時(shí)，輸入當(dāng)前鏈表左端點(diǎn) head 和中心節(jié)點(diǎn) slow 的下一個(gè)節(jié)點(diǎn) tmp(因?yàn)殒湵硎菑?slow 切斷的)。 cut 遞歸終止條件： 當(dāng)head.next == None時(shí)，說明只有一個(gè)節(jié)點(diǎn)了，直接返回此節(jié)點(diǎn)。

2，合并 merge 環(huán)節(jié)： 將兩個(gè)排序鏈表合并，轉(zhuǎn)化為一個(gè)排序鏈表。 雙指針法合并，建立輔助ListNode h 作為頭部。 設(shè)置兩指針 left, right 分別指向兩鏈表頭部，比較兩指針處節(jié)點(diǎn)值大小，由小到大加入合并鏈表頭部，指針交替前進(jìn)，直至添加完兩個(gè)鏈表。 返回輔助ListNode h 作為頭部的下個(gè)節(jié)點(diǎn) h.next。

代碼實(shí)現(xiàn)

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

讀到這里，這篇“Java雙指針法怎么使用”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點(diǎn)還需要大家自己動手實(shí)踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。