链表的中间节点. 题目即是题意, 注意如果有两个中间节点 (总节点个数为偶数) 的话, 返回第二个中间节点. 例子,
- Example 1:
- 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:
- 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.
思路是快慢指针, 快指针停下的时候, 慢指针所在的位置即是所求.
时间 O(n)
空间 O(1)
Java 实现
- class Solution {
- 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;
- }
- }
JavaScript 实现
- /**
- * @param {ListNode} head
- * @return {ListNode}
- */
- var middleNode = function(head) {
- let slow = head;
- let fast = head;
- while (fast !== null && fast.next !== null) {
- slow = slow.next;
- fast = fast.next.next;
- }
- return slow;
- };
- [LeetCode] 876. Middle of the Linked List
来源: http://www.bubuko.com/infodetail-3474662.html