当前位置：首页 > article >正文

力扣 876. 链表的中间结点【详细手写】

article 2024/10/23 5:49:46

一、题目

在这里插入图片描述

二、思路

设置快慢指针遍历链表，慢指针每次移动一个节点，快指针是慢指针速度的2倍，这样相同时间内，快指针移动的节点数就是慢指针的2倍。那么，当快指针移动到最后一个节点时，慢指针移动到中间节点的位置。大致思路为以上描述，具体需要分链表节点个数为奇数还是偶数，详细思路见下图：
在这里插入图片描述

三、代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}