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:
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.
Note:
1
and 100
.思路:
就是求出链表的终点,非常简单的题目,使用快慢指针,快指针每次走一步,慢指针每次走两步,之所以写一下,是因为很多链表类的题目,都会首先求一下链表长度,再继续往下做。比如有一道题,让把一个有序列表,从中间断开,在合并起来,变成摇摆数组之类的题目。
代码:
go:
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func middleNode(head *ListNode) *ListNode { slow , fast := head, head for fast != nil && fast.Next != nil { fast = fast.Next.Next slow = slow.Next } return slow }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句