跳到主要内容

Java程序一次迭代获取链表的中间元素

在理解这个示例之前，请确保您首先访问了以下教程，

示例 1：在单次搜索中获取 LinkedList 的中间元素​

class LinkedList {

  // 创建 Node 类的对象
  // 表示链表的头部
  Node head;

  // 静态内部类
  static class Node {
    int value;

    // 将每个节点连接到下一个节点
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {

    // 创建一个 LinkedList 对象
    LinkedList linkedList = new LinkedList();

    // 为链表的每个节点分配值
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // 连接链表的每个节点到下一个节点
    linkedList.head.next = second;
    second.next = third;

    // 打印链表
    Node pointer = linkedList.head;
    System.out.print("LinkedList: " );
    while (pointer != null) {
      System.out.print(pointer.value + " ");
      pointer = pointer.next;
    }

    // 查找中间元素
    Node ptr1 = linkedList.head;
    Node ptr2 = linkedList.head;

    while (ptr1.next != null) {

      // ptr1 每次增加 2 个节点，ptr2 每次增加 1 个节点
      // 如果 ptr1 指向最后一个元素
      // ptr2 将指向中间元素
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
      }
    }

    System.out.println("\n中间元素: " + ptr2.value);

  }
}

输出

LinkedList: 1 2 3
中间元素: 2

在上面的示例中，我们在 Java 中实现了链表数据结构。然后我们在单个循环中找到链表的中间元素。注意代码，

    while (ptr1.next != null) {

      // ptr1 每次增加 2 个节点，ptr2 每次增加 1 个节点
      // 如果 ptr1 指向最后一个元素
      // ptr2 将指向中间元素
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
      }
    }

这里，我们有两个变量 ptr1 和 ptr2。我们使用这些变量来迭代链表。

在每次迭代中，ptr1 将访问两个节点，而 ptr2 将访问链表的单个节点。

现在，当 ptr1 到达链表的末尾时，ptr2 将位于中间。通过这种方式，我们能够在单次迭代中获取链表的中间部分。

示例 2：使用 LinkedList 类获取 LinkedList 的中间元素​

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // 使用 LinkedList 类创建链表
    LinkedList<String> animals = new LinkedList<>();

    // 向 LinkedList 添加元素
    animals.add("Dog");
    animals.addFirst("Cat");
    animals.addLast("Horse");
    System.out.println("LinkedList: " + animals);

    // 访问中间元素
    String middle = animals.get(animals.size()/2);
    System.out.println("中间元素: " + middle);
    }
}

输出

LinkedList: [Cat, Dog, Horse]
中间元素: Dog

在上面的示例中，我们使用 LinkedList 类实现了链表数据结构。注意表达式，

animals.get(animals.size()/2)
  • size()/2 - 返回中间元素的位置
  • get() - 返回中间位置的元

素

最后于 更新