Javaのダブルポインタメソッドの使い方

序文

通常、リンク リストや配列などの線形データ構造で使用されます。

ポインタは、実際にはデータのインデックスまたはリンク リストのノードです。検索条件が満たされるまで、2 つのポインタが左右に移動します。ダブル ポインタは、同じ方向のダブル ポインタ、異なる方向のダブル ポインタ、高速ポインタと低速ポインタ、およびスライディング ウィンドウに分類できます。配列またはリンク リスト内の重複要素の削除、同じ方向のダブル ポインター (線形リストは順序付けする必要がある) など、ニーズに基づいてダブル ポインター モデルを選択します。通常、高速ポインターと低速ポインターは、検索などのリンク リストで使用されます。リンクされたリストの中点と、リンクされたリストがリングであるかどうかを決定します。リングがある場合は、リンクされたリストの置換の開始点、リングの長さ、およびリンクされたリストの K 番目の最後の要素を決定します。たとえば、バイナリで検索では、異方性ダブル ポインターが使用されます。スライディング ウィンドウは実際には、配列またはリンク リストの特定の間隔に対する操作です。たとえば、最長/最短の部分文字列や特定の部分文字列の長さの要件を見つけます。

1. リンク リストに循環があるかどうかを判断する

リコウ 141 の質問

リンク リストのヘッド ノード head を与え、循環があるかどうかを判断します。リンクされたリストにあります。

リンクされたリスト内に、次のポインタを継続的に追跡することによって再び到達できるノードがある場合、リンクされたリスト内にサイクルが存在します。指定されたリンク リスト内のサイクルを表すために、評価システムは内部で整数 pos を使用して、リンク リストの末尾が接続されるリンク リスト内の位置 (0 から始まるインデックス) を表します。注: pos はパラメータとして渡されません。リンクリストの実態を特定するためだけに。

リンクされたリストにリングがある場合は、true を返します。それ以外の場合は、 false を返します。

#コードの実装

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;
            //此时相遇了
            if(fast == low){
                return true;
            }
        }
        return false;
    }
}

2. リンクされたリストの中央にある要素を見つけます

Likou 876 の質問

ヘッド ノードが head である空でない単一リンク リストを指定すると、リンク リストの中間ノードが返されます。

中間ノードが 2 つある場合は、2 番目の中間ノードを返します。

コードの実装

  //快慢指针法
    public ListNode middleNode(ListNode head) {
        ListNode low = head,fast = head;
        while(fast != null && fast.next != null){
            //慢指针走一步
            low = low.next;
            //快指针走两步
            fast = fast.next.next;
        }
        //奇数，fast.next = null时，low即为所求
        //偶数，fsat == null时，low即为所求
        return low;
    }

3.奇数の前と偶数の後の奇数と偶数の並べ替え

Liqun 328 の質問

与えられた順序 リンク リストのヘッド ノード head は、奇数のインデックスを持つすべてのノードと偶数のインデックスを持つノードを結合し、並べ替えられたリストを返します。

最初のノードのインデックスは奇数とみなされ、2 番目のノードのインデックスは偶数と見なされます。

コードの実装

 public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fastHead = head.next;
        ListNode lowTail = head;//奇数链表
        ListNode fastTail = fastHead;//偶数链表
        while(fastTail != null && fastTail.next != null){
            //更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点
            lowTail.next = fastTail.next;
            lowTail = lowTail.next;
           // 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点
            fastTail.next = lowTail.next;
            fastTail = fastTail.next;
        }
        //合并两个链表
        lowTail.next = fastHead;
        return head;
    }

4. 並べ替えられたリンク リストの重複要素を削除します

Liqun 82 の質問

与えられたものソートされたリンク リストの先頭は、元のリンク リスト内の重複する番号を持つすべてのノードを削除し、異なる番号だけを残します。ソートされたリンク リストを返します

コード実装

 public ListNode deleteDuplicates(ListNode head) {
        //虚拟头节点法
        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){
                //只有一个元素
                return dummyHead.next;
            }
            if(cur.val != next.val){
                //cur不是重复节点，三指针都移动
                cur = cur.next;
                prev = prev.next;
            }else{
                //让next指针一直向后移动，直到与cur.val不相等的节点位置
                while(next != null && cur.val == next.val){
                    next = next.next;
                }
                // 此时next指向了第一个不重复的元素
                // 此时prev - next之间所有重复元素全部删除
                prev.next = next;
                cur = next;
            }
        }
        return dummyHead.next;
    }

5。3 つの数値の合計

15 の質問に正確に答えます

n 個の整数を含む配列 nums を与え、 a b c = 0 となる 3 つの要素 a、b、c が nums にあるかどうかを調べます。合計が 0 である非反復トリプルをすべて見つけてください。

注: 回答に重複したトリプルを含めることはできません。

コードの実装

 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) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                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

私があなたに差し上げますリンク リスト ヘッド ノード head と特定の値 x は、x 未満のすべてのノードが x 以上のノードの前に表示されるようにリンク リストを分離してください。

各パーティション内の各ノードの初期の相対位置を保存する必要はありません。

コードの実装

 public ListNode partition(ListNode head, int x) {
        // 创建small和big两个小链表的头节点
        ListNode smallHead = new ListNode(-1);
        ListNode bigHead = new ListNode(-1);
        // 按照升序插入，因此需要尾插
        // 分别指向两个子链表的尾部
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;
        //遍历原链表，根据值放入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. 2 つの順序付けされた配列をマージする

88 の質問と同様に

give 2 つあります。非減少順に配置された整数配列 nums1 と nums2、およびそれぞれ nums1 と nums2 の要素の数を表す 2 つの整数 m と n。結合された配列も降順に配置されるように、nums2 を nums1 に結合してください。

注: 最終的に、マージされた配列は関数によって返されるのではなく、配列 nums1 に格納される必要があります。この状況に対処するために、nums1 の初期長は m n です。ここで、最初の m 要素はマージする必要がある要素を表し、最後の n 要素は 0 であるため無視する必要があります。 nums2 の長さは 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. 2 つの数値の合計 - 順序付けされた配列を入力

167 の質問と同様に

1 から始まる添字付きの整数の配列番号を与えます。配列は減少しない順序で並べられています。配列から 2 つの数値の合計がターゲット数値 target に等しくなるように見つけてください。これら 2 つの数値がそれぞれ Number[index1] と Numbers[index2] である場合、 1 <=index1

これら 2 つの整数の添字インデックス 1 とインデックス 2 を、長さ 2 の整数配列 [インデックス 1, インデックス 2] の形式で返します。

コードの実装

 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. 最小長の部分配列

(Likou 209) n 個の正の整数を含む数値を指定すると、 と の配列が得られます。正の整数のターゲット。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

代码实现

//滑动窗口法
 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.排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

解题思路

通过递归实现链表归并排序，有以下两个环节：

1，分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）； 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。 找到中点 slow 后，执行 slow.next = None 将链表切断。 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。

2，合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。 双指针法合并，建立辅助ListNode h 作为头部。 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。 返回辅助ListNode h 作为头部的下个节点 h.next。

代码实现

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のダブルポインタメソッドの使い方の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。