Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

How to use Java double pointer method

2025-04-09 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

Shulou(Shulou.com)05/31 Report--

In this article, the editor introduces in detail "how to use Java double finger needles". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to use Java double finger needles" can help you solve your doubts.

Preface

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

A pointer is actually an index of data or a node of a linked list. The two pointers move in the left and right directions until the search criteria are met. Double pointers can be divided into double pointers in the same direction, double pointers in the opposite direction, fast and slow pointers, and sliding windows. Select a double-pointer model according to the demand, such as deleting duplicate elements in the array or linked list, double pointers in the same direction (the linear list is ordered on the premise that the linear list is ordered); fast and slow pointers are generally used in the linked list, such as finding the midpoint of the linked list, judging whether the linked list has a ring, judging the starting point of the linked list, the length of the ring, and the penultimate element of the linked list; for example, the opposite double pointer is used in binary search. A sliding window is actually an operation on an array or linked list, such as finding the length requirement of the longest / shortest substring or a specific substring.

1. Determine whether the linked list has a ring

Force to buckle 141 questions

Give you a head of the head node of the linked list to determine whether there are rings in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. To represent the rings in a given linked list, the integer pos is used within the evaluation system to indicate where the tail of the linked list is connected to the linked list (the index starts at 0). Note: pos is not passed as a parameter. Just to identify the actual situation of the linked list.

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

Code implementation

Public class Solution {/ / Fast and slow pointer public boolean hasCycle (ListNode head) {ListNode fast = head; ListNode low = head; while (fast! = null & & fast.next! = null) {fast = fast.next.next; low = low.next; / / meet if (fast = = low) {return true at this time }} return false;}} 2. Find the element in the middle of the linked list

Force buckle 876 questions

Given a non-empty single linked list whose header node is head, return the middle node of the linked list.

If there are two intermediate nodes, the second intermediate node is returned.

Code implementation

/ / public ListNode middleNode (ListNode head) {ListNode low = head,fast = head; while (fast! = null & & fast.next! = null) {/ / slow pointer takes one step low = low.next; / / Fast pointer takes two steps fast = fast.next.next } / / Odd, when fast.next = null, low is the / / even number, and when fsat = = null, low is the return low;} 3. Parity before and after parity

Force buckle 328 questions

Head, the header node of a single linked list, combines all nodes with an odd index and a node with an even index, 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;// odd linked list ListNode fastTail = fastHead / / even linked list while (fastTail! = null & & fastTail.next! = null) {/ / when updating odd nodes, the latter node of odd nodes needs to point to the latter node of even nodes lowTail.next = fastTail.next; lowTail = lowTail.next / / when updating an even node, the latter node of the even node needs to point to the latter node of the odd node fastTail.next = lowTail.next; fastTail = fastTail.next;} / / merge two linked lists lowTail.next = fastHead; return head;} 4. Delete duplicate elements of a sorted linked list

Force buckle 82 questions

Given the header head of a sorted linked list, delete all nodes with duplicate numbers in the original linked list, leaving only different numbers. Returns the sorted linked list

Code implementation

Public ListNode deleteDuplicates (ListNode head) {/ / Virtual head node method ListNode dummyHead = new ListNode (- 1); dummyHead.next = head; ListNode prev = dummyHead; ListNode cur = prev.next; while (cur! = null) {/ / introduce next pointer ListNode next = cur.next If (next = = null) {/ / there is only one element return dummyHead.next;} if (cur.val! = next.val) {/ / cur is not a duplicate node, all three pointers move cur = cur.next; prev = prev.next } else {/ / Let the next pointer move backwards until the node position while (next! = null & & cur.val = = next.val) {next = next.next } / / at this time next points to the first non-repeating element / / all repeating elements between prev-next are deleted prev.next = next; cur = next;}} return dummyHead.next;} 5. The sum of three numbers

Buckle 15 questions

Give you an array of n integers, nums, and determine if there are three elements in nums, such as a + b + c = 0. Please find all the triples whose sum is 0 and do not repeat.

Note: duplicate triples cannot be included in the answer.

Code implementation

Public List threeSum (int [] nums) {int n = nums.length; Arrays.sort (nums); List ans = new ArrayList (); / / enumerate a for (int first = 0; first)

< n; ++first) { // 需要和上一次枚举的数不相同 if (first >

0 & & nums [first] = = nums [first-1]) {continue;} / c the pointer initially points to the rightmost end of the array int third = n-1; int target =-nums [first]; / / enumerates b for (int second = first + 1; second)

< n; ++second) { // 需要和上一次枚举的数不相同 if (second >

First + 1 & & nums [second] = = nums [second-1]) {continue;} / / you need to ensure that the pointer of b is on the left while of the pointer of c (second

< third && nums[second] + nums[third] >

Target) {--third;} / / if the pointers coincide, with the subsequent increase of b, there will be no satisfying a+b+c=0 and b

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 0

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report