876. 链表的中间结点

image.png

题解

快慢指针

使用两个指针 slow 和 fast 一起遍历，slow 一次走一步，fast 一次走两步，当 fast 走到结尾时 slow 则在中间，返回 slow

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：35.8 MB, 在所有 Java 提交中击败了24.33% 的用户

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         ListNode slow = head;
  4.         ListNode fast = head;
  6.         while (fast != null && fast.next != null) {
  7.             slow = slow.next;
  8.             fast = fast.next.next;
  9.         }
  10.         return slow;
  11.     }
  12. }

使用辅助数组

链表的缺点是不能使用索引访问元素，使用额外的数组空间存储链表节点，假设链表一共有 N 个节点，则返回数组中索引为 N/2 的元素

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：35.8 MB, 在所有 Java 提交中击败了32.47% 的用户

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         ArrayList<ListNode> list = new ArrayList<>();
  4.         while (head != null) {
  5.             list.add(head);
  6.             head = head.next;
  7.         }
  8.         return list.get(list.size() / 2);
  9.     }
  10. }

遍历两次链表

第一次遍历记录节点数量 N ，第二次遍历到第 N/2 个元素，将该元素返回

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：35.8 MB, 在所有 Java 提交中击败了43.72% 的用户

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         int n = 0;
  4.         ListNode cur = head;
  5.         while (cur != null) {
  6.             cur = cur.next;
  7.             n ++;
  8.         }
  10.         cur = head;
  11.         for (int i = 0; i < n / 2; i++) {
  12.             cur = cur.next;
  13.         }
  14.         return cur;
  15.     }
  16. }