这是悦乐书的第337次更新，第361篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第206题（顺位题号是876）。给定具有头节点的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。例如：
输入：[1,2,3,4,5]
输出：此列表中的节点3（序列化：[3,4,5]）
返回的节点的值为3.（该节点的判断序列化为[3,4,5]）。
请注意，我们返回了一个ListNode对象ans，这样：
ans.val = 3，ans.next.val = 4，ans.next.next.val = 5，ans.next.next.next = NULL。
输入：[1,2,3,4,5,6]
输出：此列表中的节点4（序列化：[4,5,6]）
由于列表有两个值为3和4的中间节点，我们返回第二个节点。
注意：
- 给定列表中的节点数将介于1和100之间。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
借助数组来解。
遍历链表中的点，存入一个List中，取List的中间元素即可。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
List<ListNode> list = new ArrayList<ListNode>();
while (head != null) {
list.add(head);
head = head.next;
}
return list.get(list.size()/2);
}
}
03 第二种解法
使用快慢指针来解。
此题也可以理解为数学中的相遇问题，一个以正常速度前进的指针，一个以2倍速度前进的快指针，在快指针指向链表结尾处时，慢指针肯定处在链表的中间位置。
此解法的时间复杂度是O(N)，空间复杂度是O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
04 小结
算法专题目前已连续日更超过六个月，算法题文章206+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
