单次迭代获取 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()
- 返回中间位置的元素