876. 链表的中间结点

• 难度：简单
• 本题涉及算法： 数组 快慢指针 单指针法
• 思路： 数组 快慢指针 单指针法
• 类似题型:
  • 202. 快乐数

题目 876. 链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

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

示例

示例 1：

输入：[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.

示例 2：

输入：[1,2,3,4,5,6]    
输出：此列表中的结点 4 (序列化形式：[4,5,6])    
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。    

提示：

• 给定链表的结点数介于 1 和 100 之间。

方法一：数组

解题思路

• 根据题目所说的 链表长度最长为100，则可以遍历入参的链表，从 0 开始记录 当 head.next = null 是 即是链表的长度，通过 A[N/2] 拿到中间数据

• 链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N，对应的中间节点即为 A[N/2]。

• 这里想说的是，把数组放在空数组(空数组长度> 传入数组)里，再去拿到指定位置的数据，还是第一次看到

  java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}

方法二 快慢指针

• 思路：快指针q每次走2步，慢指针p每次走1步，当q走到末尾时p正好走到中间。

java

/**
 * 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) { // 对链表个数 奇偶的判断
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast  and fast.next :
            fast = fast.next.next
            slow = slow.next
        return slow

方法三 单指针法

• 遍历获取链表的长度 n
• 在遍历直到 n/2 的位置

  python

  ```python

class Solution: def middleNode(self, head: ListNode) -> ListNode: n, cur = 0, head while cur: n += 1 cur = cur.next k, cur = 0, head while k < n // 2: k += 1 cur = cur.next return cur ```