How to use Java double pointer method

Preface

Usually used in linear data structures, such as linked lists and arrays.

The pointer is actually the index of the data or the node of the linked list. The two pointers move in the left and right directions until the search conditions are met. Double pointers can be divided into double pointers in the same direction, double pointers in different directions, fast and slow pointers, and sliding windows. Choose a double pointer model based on your needs, such as deleting duplicate elements in an array or linked list, double pointers in the same direction (linear lists must be ordered); fast and slow pointers are generally used in linked lists, such as finding the midpoint of a linked list and determining whether a linked list is If there is a ring, determine the starting point of the linked list replacement, the length of the ring, and the Kth last element of the linked list; For example, in binary search, anisotropic double pointers are used; The sliding window is actually an operation on a certain interval of an array or linked list. For example, find the longest/shortest substring or the length requirement of a specific substring.

1. Determine whether there is a cycle in the linked list

Likou 141 Question

Give you the head node head of the linked list and determine whether there is a cycle in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, then there is a cycle in the linked list. To represent a cycle in a given linked list, the evaluation system internally uses the integer pos to represent the position in the linked list where the tail of the linked list is connected (index starting from 0). Note: pos is not passed as a parameter. Just to identify the actual situation of the linked list.

If there is a ring in the linked list, return true. Otherwise, return false .

Code Implementation

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. Find the element in the middle of the linked list

Likou 876 question

Given a A non-empty singly linked list whose head node is head returns the intermediate node of the linked list.

If there are two intermediate nodes, return the second intermediate node.

Code Implementation

  //快慢指针法
    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. Odd and even sorting before odd and after even

Liqun 328 questions

Given order The head node of the linked list, head, combines all nodes with odd indexes and nodes with even indexes together, and then returns the reordered list.

The index of the first node is considered odd, the index of the second node is even, and so on.

Code implementation

 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. Delete duplicate elements of the sorted linked list

Liqun 82 questions

Given The head of a sorted linked list removes all nodes with duplicate numbers in the original linked list, leaving only different numbers. Return the sorted linked list

Code implementation

 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. Sum of three numbers

Strongly answer 15 questions

Give you an array nums containing n integers, determine whether there are three elements a, b, c in nums such that a b c = 0? Please find all non-repeating triples whose sum is 0.

Note: Answers cannot contain duplicate triples.

Code implementation

 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. Split the linked list

Likou interview question 02.04

I will give you a linked list The head node head and a specific value x, please separate the linked list so that all nodes less than x appear before nodes greater than or equal to x.

You do not need to preserve the initial relative position of each node in each partition.

Code Implementation

 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. Merge two ordered arrays

Like the 88 questions

give You have two integer arrays nums1 and nums2 arranged in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Please merge nums2 into nums1 so that the merged array is also arranged in non-decreasing order.

Note: Ultimately, the merged array should not be returned by the function, but stored in the array nums1. To cope with this situation, nums1 has an initial length m n, where the first m elements represent elements that should be merged and the last n elements are 0 and should be ignored. The length of nums2 is n .

Code implementation

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. The sum of two numbers - input an ordered array

Like the 167 questions

Give you an integer array numbers with subscripts starting from 1. The array has been arranged in non-decreasing order. Please find two numbers from the array such that the sum of them is equal to the target number target. If these two numbers are numbers[index1] and numbers[index2] respectively, then 1 <= index1 < index2 <= numbers.length .

Return the subscripts index1 and index2 of these two integers in the form of an integer array of length 2 [index1, index2].

Code implementation

 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. Minimum length subarray

(Likou 209) Given a number containing n positive integers An array of and a positive integer target.

找出该数组中满足其和 ≥ 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;
    }

The above is the detailed content of How to use Java double pointer method. For more information, please follow other related articles on the PHP Chinese website!