search
HomeJavajavaTutorialHow to use Java double pointer method

How to use Java double pointer method

Apr 18, 2023 pm 08:34 PM
java

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 .

How to use Java double pointer method

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.

How to use Java double pointer method

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.

How to use Java double pointer method

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

How to use Java double pointer method

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.

How to use Java double pointer method

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.

How to use Java double pointer method

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 .

How to use Java double pointer method

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

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

How to use Java double pointer method

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

How to use Java double pointer method

代码实现

//滑动窗口法
 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 ,请将其按 升序 排列并返回 排序后的链表 。

How to use Java double pointer method

解题思路

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

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!

Statement
This article is reproduced at:亿速云. If there is any infringement, please contact admin@php.cn delete
Why does the browser fail to correctly process the 401 status code when developing a WebSocket server using Netty?Why does the browser fail to correctly process the 401 status code when developing a WebSocket server using Netty?Apr 19, 2025 pm 07:21 PM

在使用Netty开发WebSocket服务器时,可能会遇到浏览器在尝试连接时未能正确处理服务器返回的401状态码的情况。 �...

Java compilation failed: What should I do if the javac command cannot generate the class file?Java compilation failed: What should I do if the javac command cannot generate the class file?Apr 19, 2025 pm 07:18 PM

Java compilation failed: Running window javac command cannot generate class file Many Java beginners will encounter this problem during the learning process: running window...

How to correctly divide business logic and non-business logic in hierarchical architecture in back-end development?How to correctly divide business logic and non-business logic in hierarchical architecture in back-end development?Apr 19, 2025 pm 07:15 PM

Discussing the hierarchical architecture problem in back-end development. In back-end development, common hierarchical architectures include controller, service and dao...

Java compilation error: How do package declaration and access permissions change after moving the class file?Java compilation error: How do package declaration and access permissions change after moving the class file?Apr 19, 2025 pm 07:12 PM

Packages and Directories in Java: The logic behind compiler errors In Java development, you often encounter problems with packages and directories. This article will explore Java in depth...

Is JWT suitable for dynamic permission change scenarios?Is JWT suitable for dynamic permission change scenarios?Apr 19, 2025 pm 07:06 PM

JWT and Session Choice: Tradeoffs under Dynamic Permission Changes Many Beginners on JWT and Session...

How to properly configure apple-app-site-association file in pagoda nginx to avoid 404 errors?How to properly configure apple-app-site-association file in pagoda nginx to avoid 404 errors?Apr 19, 2025 pm 07:03 PM

How to correctly configure apple-app-site-association file in Baota nginx? Recently, the company's iOS department sent an apple-app-site-association file and...

What are the differences in the classification and implementation methods of the two consistency consensus algorithms?What are the differences in the classification and implementation methods of the two consistency consensus algorithms?Apr 19, 2025 pm 07:00 PM

How to understand the classification and implementation methods of two consistency consensus algorithms? At the protocol level, there has been no new members in the selection of consistency algorithms for many years. ...

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.