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

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:算法-二分法


下一篇:【数组】剑指Offer:旋转数组的最小数字