长大后想做什么？做回小孩！

0%

LeetCode——链表的中间结点

发表于 分类于 Valine：
本文字数： 166

NO.876 链表的中间结点 简单

8o8VEQ.png

思路一：单指针

单指针先遍历一遍，统计节点数，然后再从头遍历找到n/2位置的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode middleNode(ListNode head) {
    //统计节点个数
    int n=0;
    ListNode curr=head;
    while (curr != null) {
        n++;
        curr=curr.next;
    }
    //找到中间位置节点
    int kth=0;
    curr=head;
    while (kth < n / 2) {
        kth++;
        curr=curr.next;
    }
    return curr;
}

时间复杂度：O(n)

思路二：快慢指针

快慢指针从头开始移动，快指针每次移动两个节点，慢指针每次移动一个节点，当快指针到达结尾，慢指针就在中间。

1
2
3
4
5
6
7
8
public ListNode middleNode(ListNode head) {
    ListNode fast=head,slow=head;
    while (fast != null && fast.next != null) {
        fast=fast.next.next;
        slow=slow.next;
    }
    return slow;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github