LeetCode876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

1
2
3
4
5
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

1
2
3
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

思路

  • 快慢指针:一个走两步,一个走一步,走得快的到null时,走得慢的在中间。

My Code in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* p1 = head;
ListNode* p2 = head;
while (p1)
{
if(p1->next)
p1 = p1->next->next;//1.不能用p++,链表不是物理存储的
//2.member access within null pointer of type 'struct ListNode,需要判空
else
{
break;//2.p1已经是尾节点,就跳出
}
p2 = p2->next;
}
return p2;
}
};

细节

  1. 不能用p++,链表不是物理存储的
  2. 使用p1 = p1->next->next时,需要判空,否则会出member access within null pointer of type ‘struct ListNode..的runtime error.如果p1已经是尾节点,p2就不要再走了,p2就是中间节点。

LC高票

Code in C++

1
2
3
4
5
6
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next)
slow = slow->next, fast = fast->next->next;
return slow;
}

人家直接在while里一次把判空做好了。。。

Code in Python

1
2
3
4
5
6
def middleNode(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow

总结

  • 快慢指针。
  • 鲁棒性测试:直接fast&&fast->next一起判空。
Thanks for Support.