Several problems related to linked lists with loops

Several problems related to linked lists with loops

2021/04/22

Preface

The following linked list is a linked list with loops, the entry of the loop is 2, and the length of the loop is 4.

The linked list nodes are defined as follows:

//Singly linked list node definition, refer to Leetcode class ListNode < T > { public T val; public ListNode<T> next; public ListNode () { this ( null , null ); } public ListNode (T val) { this (val, null ); } public ListNode (T val, ListNode next) { this .val = val; this .next = next; } } Copy code

Determine whether the linked list has a ring

Determining whether there is a ring list, a better approach is speed pointer method .

Define two pointers

fast, slow
, Initially all point to the head node. Fast pointer
fast
Move backward one bit at a time, slow pointer
slow
Move backward two bits at a time; if the fast and slow pointers meet (point to the same node and are not empty), it means that there is a ring in the linked list.

//Determine whether the linked list has a loop public boolean isLoop () { if ( this .head == null ){ return false ; } ListNode<T> fast = head; ListNode<T> slow = head; while (fast != null && fast.next != null ) { fast = fast.next.next; slow = slow.next; if (fast == slow){ return true ; } } return false ; } Copy code

Determine the ring entrance

If there are rings in the linked list, how to determine which node is the entrance of the ring (the node where the rings meet)?

Suppose the entry of the linked list ring is

entrance
, The node where the fast and slow pointers meet is
meet
, Since the speed of the fast pointer is twice that of the slow pointer, when the fast and slow pointers meet, the distance traveled by the slow pointer is
s
, The distance traveled by the fast pointer is
2s
.

Suppose the distance from the head node to the ring entrance is

he
, The distance from the ring entrance to the meeting node is
em
, The length of the loop is
r
.

We can get:

s=he+em2s=he+em+n rs = he + em/2s = he + em + n*r

among them,

n
Indicates the number of turns of the ring that the fast hand travels. and sos=n rs = n*r , that is, the distance traveled by the slow pointer is an integer multiple of the ring length when they meet.

Suppose the length of the linked list is

L
,Have
L = he + r
,then

s=he+em=n r=(n 1) r+r=(n 1) r+L hes = he + em = n*r = (n-1)*r + r = (n-1)*r + L-he

get

he=(n 1) r=L he em=(n 1) r+r emhe = (n-1)*r = L-he-em = (n-1)*r + r-em

I.e. , if the meeting point is moved backward from the head node and at the same speed, go through

n-1
A ring that can meet at the entrance of the ring .

So we get the method of how to get the ring entry:

  • Find the node where the fast and slow pointers meet
    meet
  • Define two pointers, pointing to
    head
    with
    meet
  • The two pointers move backward at the same time until the two pointers point to the same node, which is the entrance to the ring
public ListNode getLoopEntrance () { if ( this .head == null ){ return null ; } ListNode<T> meet = null ; ListNode<T> fast = head; ListNode<T> slow = head; while (fast != null && fast.next != null ) { fast = fast.next.next; slow = slow.next; if (fast == slow){ meet = fast; break ; } } //meet == null means there is no ring in the linked list if there is no meeting if (meet == null ){ return null ; } //The fast and slow pointer moves backwards at the same speed from the point of meeting fast = head; slow = meet; while (fast != slow){ fast = fast.next; slow = slow.next; } return fast; } Copy code

Determine the length of the loop

On a ring, the difference between the fast and slow pointer speeds is twice. Starting from the meeting node, the fast and slow pointers move backwards at their respective speeds in turn, and the length of the slow pointer increases by 1 when the fast and slow pointers meet. The distance traveled by the slow pointer is the length of the loop when the fast and slow pointers meet.

public int getLoopLength () { if (head == null || head.next == null ) { return - 1 ; } ListNode<T> fast = head.next; ListNode<T> slow = head.next; boolean isLoop = false ; while (fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; if (slow == fast) { isLoop = true ; break ; //At this time fast and slow meet for the first time } } //If the linked list has no loops, return 0 if (!isLoop){ return 0 ; } //Has already met, len is initially 1, and the speed pointer continues to move backward int len = 1 ; slow = slow.next; fast = fast.next.next; while (slow != fast) { slow = slow.next; fast = fast.next.next; len++; } return len; } Copy code