LeetCode0876. 链表的中间结点

一. 题目

1. 题目
   给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
   如果有两个中间结点，则返回第二个中间结点。

2. 示例
   

二. 方法一: 数组

1. 解题思路

   1. 用链表中的数据存放在列表中
   2. 数组的长度就等于链表的长度
   3. 读取中间位置的元素即可

2. 解题代码

   # class ListNode:
   #     def __init__(self, x):
   #         self.val = x
   #         self.next = None
   
   class Solution:
       def middleNode(self, head: ListNode) -> ListNode:
       	# 将链表的头节点放入到数组中
           arr = [head]
           # 判断当前节点指向的下一个节点是否为空
           while arr[-1].next:
           	# 将下一个节点元素插入到数组中
               arr.append(arr[-1].next)
           # 返回中间节点即可
           return arr[len(arr) // 2]
   

3. 分析
   时间复杂度: O(n)
   空间复杂度: O(n)

三. 方法二: 单指针

1. 解题思路

   1. 先遍历链表, 用于读取链表的长度
   2. 然后再遍历一次链表, 当遍历到中间位置时,输出结果即可

2. 解题代码

   def middleNode(self, head: ListNode) -> ListNode:
       size, count = 0, 0
       # cur指针指向head头节点
       cur = head
       # 获取链表的长度
       while cur:
           size += 1
           cur = cur.next
       # cur指针指向head头节点
       cur = head
       # 遍历到中间节点
       while count < size // 2:
           cur = cur.next
           count += 1
       # 输出中间节点的值
       return cur
   

3. 分析
   时间复杂度: O(n)
   空间复杂度: O(1)

四. 方法三: 快慢指针

1. 解题思路

   1. 创建快慢指针left, right. 并同时指向head头节点
   2. 然后快指针每移动2次, 慢指针就移动一次, 这样慢指针始终是所遍历过的列表的中点
   3. 当right或right.next是尾节点时, left节点恰好在中点
   4. 返回此时left的值即可

2. 解题代码

   def middleNode(self, head: ListNode) -> ListNode:
       left = right = head
       while right and right.next:
           left = left.next
           right = right.next.next
       return left
   

3. 分析
   时间复杂度: O(n)
   空间复杂度: O(1)