This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Circular Linked List (141)

Topic describes

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.

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There are no loops in the linked list.Copy the code

The advanced

Can you solve this problem with O(1){O(1)}O(1) memory?

Pay attention to

  • The number of nodes in a linked list ranges from[0, 104]
  • -105 <= Node.val <= 105
  • pos 为 - 1Or one of the linked listsEffective index 。

Thought analysis

If the list has rings, you iterate two at a time with a fast pointer, and you iterate one at a time with a slow pointer, and if there are rings, those two Pointers will eventually intersect.

The code shown

Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

public static boolean hasCycle(ListNode head) {
        ListNode quick = head;
        ListNode slow = head;
        while(quick ! =null&& quick.next ! =null){
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow){
                return true; }}return false;
    }
Copy the code

Middle node of linked list (876)

Topic describes

Given a non-empty singly linked list with head, return the middle node of the list. If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input: [1,2,3,4,5] output: node 3 in this list (serialized form: [3,4,5]) returns the value of node 3. (the serialization statement of this node in the evaluation system is [3,4,5]). Val = 3, ans.next-val = 4, ans.next-next-val = 5, and ans.next-next-next = NULL.Copy the code

Example 2:

Input: [1,2,3,4,5,6] output: node 4 in this list (serialized form: [4,5,6]) since the list has two intermediate nodes with values of 3 and 4, we return the second node.Copy the code

prompt

  • The number of nodes in a given linked list is between1 和 100In between.

Thought analysis

One fast pointer, two at a time, one slow pointer, one at a time, the fast pointer reaches the end, the slow pointer reaches the midpoint.

The code shown

Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

    public static ListNode middleNode(ListNode head) {  / / 6
        // Double pointer solution
        if (head == null) {
            return null;
        }
        ListNode quick = head;
        ListNode slow = head;
        while(quick ! =null&& quick.next ! =null) {
            quick = quick.next.next;
            slow = slow.next;
        }
        return slow;

        // Single pointer solution
        // Put it in an array
    }
Copy the code

conclusion

Double pointer solution is quite common in linked lists and needs to be well mastered.