LinkedList - 876. Middle of the Linked List

1. 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:

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:

• The number of nodes in the given list will be between 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
}