单次迭代获取 LinkedList 中间元素的 Java 程序

要理解此示例，请确保您首先访问以下教程，

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

public class LinkedList {

  // create an object of Node class
  // represent the head of the linked list
  Node head;

  // static inner class
  static class Node {
    int value;

    // connect each node to next node
    Node next;

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

  public static void main(String[] args) {

    // create an object of LinkedList
    LinkedList linkedList = new LinkedList();

    // assign values to each linked list node
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // connect each node of linked list to next node
    linkedList.head.next = second;
    second.next = third;

    // print the linked list
    Node pointer = linkedList.head;
    System.out.print("LinkedList: " );
    while (pointer != null) {
      System.out.print(pointer.value + " ");
      pointer = pointer.next;
    }

    // Find the middle element
    Node ptr1 = linkedList.head;
    Node  `ptr2`  = linkedList.head;

    while (ptr1.next != null) {

      // increase the ptr1 by 2 and  `ptr2`  by 1
      // if ptr1 points to last element
      //  `ptr2`  will points to middle element
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
         `ptr2`  =  `ptr2` .next;
      }
    }

    System.out.println("\nMiddle Element: " +  `ptr2` .value);

  }
}

输出

LinkedList: 1 2 3
Middle Element: 2

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

    while (ptr1.next != null) {

      // increase the ptr1 by 2 and  `ptr2`  by 1
      // if ptr1 points to last element
      //  `ptr2`  will points to middle element
      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;

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

    // create a linked list using the LinkedList class
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.addFirst("Cat");
    animals.addLast("Horse");
    System.out.println("LinkedList: " + animals);

    // access middle element
    String middle = animals.get(animals.size()/2);
    System.out.println("Middle Element: " + middle);
    }
}

输出

LinkedList: [Cat, Dog, Horse]
Middle Element: Dog

在上面的例子中，我们使用了 LinkedList 类来实现链表数据结构。注意这一行，

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