Java 이중 포인터 방법을 사용하는 방법

머리말

일반적으로 연결된 목록 및 배열과 같은 선형 데이터 구조에 사용됩니다.

포인터는 실제로 데이터의 인덱스이거나 연결 목록의 노드입니다. 두 개의 포인터는 검색 조건이 충족될 때까지 왼쪽과 오른쪽 방향으로 이동합니다. 이중 포인터는 같은 방향의 이중 포인터, 다른 방향의 이중 포인터, 빠르고 느린 포인터, 슬라이딩 창으로 나눌 수 있습니다. 필요에 따라 이중 포인터 모델을 선택하십시오(예: 배열 또는 연결 목록에서 중복 요소 삭제, 같은 방향의 이중 포인터(선형 목록은 순서가 지정되어야 함)). 빠른 포인터와 느린 포인터는 일반적으로 찾기와 같이 연결 목록에서 사용됩니다. 연결 리스트의 중간점과 연결 리스트가 있는지 판단 링이 있는 경우 연결 리스트 교체의 시작점, 링의 길이, 연결 리스트의 K번째 마지막 요소를 결정합니다. 예를 들어 이진수로; 검색, 이방성 이중 포인터가 사용됩니다. 슬라이딩 윈도우는 실제로 배열 또는 연결 목록의 특정 간격에 대한 작업입니다. 예를 들어 가장 긴/가장 짧은 하위 문자열 또는 특정 하위 문자열의 길이 요구 사항을 찾습니다.

1. 연결리스트에 순환이 있는지 확인

누가복음 141장 질문

연결리스트의 헤드 노드 헤드가 주어지고, 연결리스트에 순환이 있는지 확인합니다.

연결된 목록에 다음 포인터를 계속 추적하여 다시 도달할 수 있는 노드가 있으면 연결 목록에 순환이 있는 것입니다. 주어진 연결 목록에서 순환을 표현하기 위해 평가 시스템은 내부적으로 정수 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. 연결 리스트의 중간에 있는 요소를 찾습니다.

Liqun 876 질문

헤드 노드가 헤드인 비어 있지 않은 단일 연결 리스트가 주어지면 중간 노드를 반환합니다. 연결리스트.

중간 노드가 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

단일 연결 리스트의 헤드 노드 헤드가 주어지면 모든 노드를 홀수 인덱스로 결합하고 노드를 짝수 인덱스로 결합합니다. 함께 넣은 다음 재정렬된 목록을 반환합니다.

첫 번째 노드의 인덱스는 홀수로 간주되고, 두 번째 노드의 인덱스는 짝수로 간주됩니다.

코드 구현

 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. 세 숫자의 합

15개 질문

nums b, c에 세 개의 요소 a가 포함되어 있는지 확인하세요. , a + b + c = 0이 되도록 합니까? 합계가 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. 연결리스트 분할

Liqun 면접 질문 02.04

연결리스트의 헤드 노드 헤드와 특정 값 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. 두 개의 순서 배열을 병합합니다

88개의 질문을 클릭하세요

비감소 순서로 정렬된 두 개의 정수 배열 nums1 및 nums2와 숫자를 나타내는 두 개의 정수 m 및 n이 제공됩니다. 각각 nums1과 nums2의 요소 수입니다. 병합된 배열도 내림차순으로 정렬되지 않도록 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. 두 숫자의 합 - 정렬된 배열 입력

질문 167을 구현하세요

1부터 시작하는 첨자가 감소하지 않는 정수 배열 숫자가 주어집니다. , 합계가 목표 숫자 목표와 동일하도록 배열에서 두 숫자를 찾으십시오. 두 숫자가 각각 숫자[index1] 및 숫자[index2]이면 1 <= index1 < index2 <= number.length 입니다.

이 두 정수의 인덱스 index1과 index2를 길이 2의 정수 배열 [index1, index2] 형식으로 반환합니다.

코드 구현

 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!