leetcode第876题，链表的中间结点。采用双指针的算法来完成。

LeetCode 876链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

1输入：[1,2,3,4,5]
2输出：此列表中的结点 3 (序列化形式：[3,4,5])
3返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
4注意，我们返回了一个 ListNode 类型的对象 ans，这样：
5ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

1输入：[1,2,3,4,5,6]
2输出：此列表中的结点 4 (序列化形式：[4,5,6])
3由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

  • 给定链表的结点数介于 1 和 100 之间。

思路

这题本质还是双指针

  1. 采用两个快慢指针，慢指针每次移动一个单位，快指针每次移动两个单位
  2. 快指针当前结点或者是快指针后一个结点为null，那么当前慢指针指向的位置即为中间结点

解题

 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11class Solution {
12    //快慢双指针
13    public ListNode middleNode(ListNode head) {
14        if(null == head) return null;
15        ListNode fast = head;
16        ListNode slow = head;
17
18        while(null != fast && null != fast.next)
19        {
20            fast = fast.next.next;
21            slow = slow.next;
22        }
23        return slow;
24    }
25}