This is the 16th day of my participation in the August Text Challenge.More challenges in August

Today use JavaScript to brush the linked list problem ~~

First, determine whether it is a circular list

141. Circular linked lists

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

Returns true if there are rings in the list. Otherwise, return false.

Advanced: Can you solve this problem with O(1) (i.e., constant) memory?

Example 1:

Enter: head = [3.2.0, -4], pos = 1Output:trueExplanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0Output:trueExplanation: A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = -1Output:falseExplanation: There are no rings in the linked list.Copy the code

Tip:

The number of nodes in the list ranges from [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list.

Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Fast and slow pointer

Set two Pointers, one that takes one step at a time called slow and the other that takes two steps at a time called fast.

When the list is loopless, the fast pointer reaches the end of the list first.

When a linked list has a loop, two Pointers will loop through the loop and eventually meet at a node.

Code implementation

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
 
/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    if(head == null) {
        return false;
    }
    let fast =head, slow = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            return true; }}return false;
};
Copy the code

Second, judge whether it is a ring list and determine the starting point of the ring

142. Circular linked List II

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

Advanced: Can you solve this problem using O(1) space?

Example 1:

Enter: head = [3.2.0, -4], pos = 1Output: Returns the index as1A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0Output: Returns the index as0A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = -1Output: returnnullExplanation: There are no rings in the linked list.Copy the code

Tip:

The number of nodes in the list is in the range [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list

Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Fast and slow pointer

When I have a ring,

Suppose that when the slow pointer walks to the starting distance of the ring is A, then the fast pointer walks 2a distance;

Suppose that the distance between the fast pointer and the starting point of the ring is x, then when the fast pointer moves 2x, the slow pointer moves x, and the fast and slow Pointers just meet.

Since x+a is the length of a ring, the slow pointer continues a step to reach the beginning of the ring;

If the slow pointer is started from the beginning, it will also reach the starting point of the ring when it takes a step. Therefore, the length of A can be seen when the slow pointer and the slow pointer reach the starting point of the ring at the same time.

Code implementation

/**js * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; */ ** @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) head, slow = head; // While (fast && fast. Next) {slow = slow. Next; fast = fast.next.next; // If (fast === slow) {// If (fast === slow) {// If (fast === slow) { while(slow ! == fast) { slow = slow.next; fast = fast.next; } return fast; }} return null if the fast pointer is null; };Copy the code