重庆网页设计培训学校_视频链接生成网站_seo实战培训费用_网站优化最为重要的内容是

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

思路

对任意正整数 n，中间结点的编号可以表示成 ⌊2n​⌋+1。 

解法一 

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int val=0, ListNode next=null) {*         this.val = val;*         this.next = next;*     }* }*/
public class Solution {public ListNode MiddleNode(ListNode head) {int n = 0;ListNode temp = head;while(temp != null){n++;temp = temp.next;}int middleCount = n / 2 + 1;temp = head;for(int i = 1; i < middleCount; i++){temp = temp.next;}return temp;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次得到链表的结点数量，然后遍历链表定位到链表的中间结点。

• 空间复杂度：O(1)。

 解二 快慢指针

public class Solution {public ListNode MiddleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。快指针遍历链表一次，慢指针遍历链表的前半段一次。

• 空间复杂度：O(1)。