Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "what is the operation of java single-chain bracelet". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Determine whether there is a ring in the linked list

Let's take a look at a picture:

We can see clearly that there are rings in this single linked list. So when using code, how can you tell if it has a ring?

Don't look at the code in a hurry, first analyze it with A Fan. With ideas, the code is relatively easy to implement.

To determine whether there are rings in the linked list, you can start from the header node and traverse each node in the single linked list in turn. Every time a node is traversed, it is compared with all the previous nodes. if it is found that the new node is the same as the previous node, it means that the node has been traversed twice, indicating that the linked list has rings, and vice versa.

But if you take a closer look at this method, you will find that it is time-consuming and laborious, because each time you traverse a node, you have to compare it with all the previous nodes. Don't worry, A Fan also has a very ingenious method, which is to use two pointers. In this way, you can think like this:

Use two pointers, a fast pointer and a slow pointer. The fast pointer takes two steps at a time, and the slow pointer takes one step at a time. If there is no ring in the linked list, the fast pointer points to null first. If there is a ring in the linked list, the fast pointer must meet.

Get through the idea, and we can use the code to implement it:

/ * *

* determine whether the linked list has rings

, /

Public class IsHasLoop {

Public static class Node {

Private int data

Private Node next

Public Node (int data,Node next) {

This.data=data

This.next=next

}

Public int getData () {

Return data

}

}

Public static void main (String [] args) {

/ / initialize single linked list

Node node5=new Node (5dint null)

Node node4=new Node (4 focus Node 5)

Node node3=new Node (3 # Node4)

Node node2=new Node (2 focus Node 3)

Node node1=new Node (1 # Node2)

/ / Let the pointer of node5 point to node1 to form a ring

Node5.next=node1

Boolean flag=isHasLoop (node1)

System.out.println (flag)

}

Public static boolean isHasLoop (Node list) {

If (list = = null) {

Return false

}

Node slow=list

Node fast=list

While (fast.next! = null & & fast.next.next! = null) {

/ / slow pointer takes one step, fast pointer takes two steps

Slow=slow.next

Fast=fast.next.next

/ / if the fast and slow pointers meet, it means there are rings in the linked list.

If (slow==fast) {

Return true

}

}

/ / conversely, there are no rings in the linked list.

Return false

}

}

Find the length of the ring

Now that the problem of judging whether there is a ring in the linked list has been solved, A Fan thinks that it can't stop here, so the train of thought spreads out for a while. Now that there is a ring, what should I do if I want to ask for the length of the ring?

Now that the fast and slow pointers meet, A Fan records the position at this time, and then let the full pointer move forward, one step at a time, so that when the slow pointer reaches the position where it met again, the length of the slow pointer is the length of the ring.

Public static int getLength (Node list) {

/ / define the initial value of ring length as 0

Int loopLength=0

Node slow=list

Node fast=list

While (fast! = null & & fast.next! = null) {

/ / slow pointer takes one step, fast pointer takes two steps

Slow=slow.next

Fast=fast.next.next

/ / jump out of the cycle when you first meet

If (slow = = fast) break

}

/ / if the fast next pointer first points to the null pointer, indicating that the linked list does not have a ring, the ring length is 0

If (fast.next = = null | | fast.next.next = = null) {

Return 0

}

/ / if there is a ring, use temporary variables to save the current linked list

Node temp = slow

/ / keep the slow pointer going until it reaches its original position.

Do {

Slow = slow.next

LoopLength++

} while (slow! = temp)

Return loopLength

}

Find the ring point

Now that there is a ring and the length of the ring is calculated, then the entry point should also be known, right? A fan was a little confused about the problem of finding the ring point, so he drew a picture:

As shown in the figure above, we assume:

The distance between the entry point and the head node is D, the distance between the ring entry point and the first encounter point is shorter, the distance between the S1 ring entry point and the first encounter point is S2, when the two pointers meet for the first time, the slow pointer only takes one step at a time, then the distance taken by the D+S1 fast pointer is 2 steps at a time, and it takes an extra n (n > = 1) circle, then the distance it goes is: D+S1+n (S1+S2) the speed of the fast pointer is twice that of the slow pointer. Then: 2 (D+S1) = D+S1+n (S1+S2) the upper equation can be obtained by finishing: d = (nmur1) (S1+S2) + S2

If (nMel 1) (S1+S2) is 0, is D and S2 equal? In other words, when the two pointers meet for the first time, as long as one of the pointers is put back to the head node position, the other pointer remains at the first meeting point, and the next two pointers take one step forward each time, and then when the two pointers meet, it is the required entry point.

It's kind of like doing a math problem, but fortunately, Fan's math skills are still so lost.

Based on the above ideas, the code is easy to implement:

Public static Node entryNodeOfLoop (Node list) {

Node slow=list

Node fast=list

While (fast.next! = null & & fast.next.next! = null) {

/ / slow pointer takes one step, fast pointer takes two steps

Slow=slow.next

Fast=fast.next.next

/ / jump out of the cycle when you first meet

If (slow = = fast) break

}

/ / if the fast next pointer first points to the null pointer, indicating that the linked list does not have a ring, then the entry point is null

If (fast.next = = null | | fast.next.next = = null) {

Return null

}

/ / after the first encounter, let one pointer point to the head node and the other pointer at the meeting position

/ / the two pointers take one step at a time until they meet, and the meeting node is the entry point.

Node head=list; / / header node

Node entryNode=slow; / / encounter node

While (entryNode! = head) {

EntryNode=entryNode.next

Head=head.next

}

Return entryNode

} "what are the operations of the java single-chain bracelet" is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.