• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The second day of leetcode brush questions, mainly about double Pointers

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

Tip:

The number of nodes in a given linked list is between 1 and 100.

The problem solving

Use the fast and slow pointer. The fast pointer moves forward at 1 times the speed, and the slow pointer moves forward at 0.5 times the speed. (Use the movement count % 2 to control 0.5 times)

Note: Since the even-numbered nodes, the latter node needs to be returned. So we need to move the slow Pointers together on the first of two moves of the fast pointer, so we need to increase the number of moves at the beginning of the loop

int count = 0; ListNode left = head; ListNode right = head; while (null ! = right.next) { count ++; right = right.next; if (count % 2 == 1) { left = left.next; } } return left;Copy the code