Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to find the middle node of the linked list". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Topic: find the middle node of the linked list

Given a non-empty single linked list whose header node is head, return the middle node of the linked 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

The node value returned is 3. (serialized form: [3pd4pm 5]).

(the serialization of the node is described by the evaluation system as [3pr 4je 5]. Notice that we return an object of type ListNode ans, such as ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2: input: [1, 2, 3, 4, 5, 6] output: node 4 in this list

(serialization form: [4pc5pcm6])

Since the list has two intermediate nodes with values of 3 and 4, we return to the second node.

Solution one

The meaning of the topic is relatively simple, that is, to find the middle node.

The first thing that comes to mind is to calculate the total length of the linked list, and then traverse to the middle node:

Public ListNode middleNode (ListNode head) {int n = 0; ListNode cur = head; while (cur! = null) {nkeeper; cur = cur.next;} int k = 0; cur = head; while (k < n / 2) {kryptonite; cur = cur.next;} return cur }

Time complexity

It was traversed once and a half. Remove the constant and the time complexity is O (n).

Space complexity

Only one linked list node is used, and the space complexity is O (1).

Solution two

Do you remember the algorithm problem of finding the nth node at the end of the last article? A solution called fast-slow pointer is used.

It can still be used here. You may be confused. The last time you knew there were n nodes apart between the two pointers, how to use them this time?

If we move the slow pointer one grid at a time and the fast pointer two at a time, is the fast pointer twice the steps of the slow pointer every time?

So that when the fast pointer moves to the tail, the slow pointer happens to be in the middle node.

Public ListNode middleNode (ListNode head) {ListNode slow = head; ListNode fast = head; while (fast! = null & & fast.next! = null) {slow = slow.next; fast = fast.next.next;} return slow;}

Here, because the fast has to move two steps each time, you need to determine whether the current node and the next node are empty.

Slow 1 2 3 4 5 6 fast 1 3 5 7 9 11

The above example is the number of nodes to which the speed pointer will go:

If the linked list is an odd number, for example, [1], then the speed node will go to 3 and 5.

If the linked list is an odd number, for example, [1 meme2, 3, 4, 5, 5, 6], then the fast and slow nodes will go to 4 and null.

This is the end of the content of "how to find the middle node of the linked list in LeetCode". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.