LeetCode.876-链表的中间节点(Middle of the Linked List)

这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！