快慢指针法

1.输入链表头节点，奇数长度返回中点，偶数长度返回上中点

暴力 #

public Node right1(Node head) {
  if (head == null)
    return null;

  Node cur = head;
  ArrayList<Node> arr = new ArrayList<>();
  while (cur != null) {
    arr.add(cur);
    cur = cur.next;
  }
  return arr.get((arr.size() - 1) / 2);
}

快慢指针法 #

public Node midOrUpMidNode(Node head) {
  if (head == null || head.next == null || head.next.next == null)
    return head;

  Node slow = head.next, fast = head.next.next;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

2.输入链表头节点，奇数长度返回中点，偶数长度返回中下点

暴力 #

public Node right2(Node head) {
  if (head == null) {
    return null;
  }
  Node cur = head;
  ArrayList<Node> arr = new ArrayList<>();
  while (cur != null) {
    arr.add(cur);
    cur = cur.next;
  }
  return arr.get(arr.size() / 2);
}

快慢指针法 #

 public Node midOrDownMidNode(Node head) {
  if (head == null || head.next == null)
    return head;

  Node slow = head.next, fast = head.next;

  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

3.输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个

暴力 #

public Node right3(Node head) {
  if (head == null || head.next == null || head.next.next == null) {
    return null;
  }
  Node cur = head;
  ArrayList<Node> arr = new ArrayList<>();
  while (cur != null) {
    arr.add(cur);
    cur = cur.next;
  }
  return arr.get((arr.size() - 3) / 2);
}

快慢指针法 #

public Node midOrUpMidPreNode(Node head) {
  if (head == null || head.next == null || head.next.next == null)
    return head;

  Node slow = head, fast = head.next.next;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

4.输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

暴力 #

public Node right4(Node head) {
  if (head == null || head.next == null) {
    return null;
  }
  Node cur = head;
  ArrayList<Node> arr = new ArrayList<>();
  while (cur != null) {
    arr.add(cur);
    cur = cur.next;
  }
  return arr.get((arr.size() - 2) / 2);
}

快慢指针法 #

public Node midOrDownMidPreNode(Node head) {
  if (head == null || head.next == null)
    return null;

  if (head.next.next == null)
    return head;

  Node slow = head, fast = head.next;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}