Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

1. Title Description

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

Tip:

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

Second, train of thought analysis

Let’s start with the simplest idea. If you want to know the middle node, you need to know the length of the list.

But from the information in the question, we only know that this is a single linked list, but we don’t know its length.

At this point you can consider first traversing the list of nodes, count the length of the list, and then calculate the median, this time you can get the middle node.

Code implementation

class Solution {
    public ListNode middleNode(ListNode head) {
        // Iterate to get the list length
        ListNode temp = head;
        int n = 0;
        while(temp ! =null) {
            ++n;
            temp = temp.next;
        }
        // Get the position of the middle node
        int middle = (n >> 1) + 1;
        // Move to the middle node
        while (middle > 1) {
            head = head.next;
            --middle;
        }
        returnhead; }}Copy the code

From the code implementation, we can see that the space complexity is O(1) and the time complexity is O(n).

Is there a more elegant way?

It is known that the speed of the rabbit is twice as fast as that of the rabbit. The rabbit starts from the middle of the path, and the rabbit starts from the beginning of the path. Can they meet at the end of the path?

The answer is yes, we’ll meet. We can figure it out.

Now the small white rabbit and the big white rabbit to turn back, excuse me, when the big white rabbit ran back to the starting point, the small white rabbit ran to what position? That’s right, the midpoint, which is the key solution to this problem

Create a fast or slow pointer. When the fast pointer reaches the end point, the slow pointer reaches the starting point. And the fast and slow Pointers only need to traverse one side of the list, compared with the above calculation of the length of the solution, there is no second operation to find the middle position.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode bigRabbit = head;
        ListNode smallRabbit = head;
        // This step is important to determine which node cannot be empty
        while(bigRabbit ! =null&& bigRabbit.next ! =null) {
            smallRabbit = smallRabbit.next;
            bigRabbit = bigRabbit.next.next;
        }
        returnsmallRabbit; }}Copy the code

From the code implementation, we can see that the space complexity is O(1) and the time complexity is O(n).

conclusion

The linked list problem is basically the operation of traversing the linked list to solve the problem. If multiple traversals are needed, we can give priority to whether we can use multiple Pointers, each pointer representing one traversal, so as to reduce the number of traversals and improve the query efficiency.