一、想简单点儿
public static void main(String[] args) {
LinkedDemo();
}
public static void LinkedDemo() {
LinkedList<String> linkedList = new LinkedList();
// 1个元素无中间元素，两个元素无中间元素，3个元素1，4个2，5个1，6个2，7个1，8个2
linkedList.add("df");
linkedList.add("xxh");
linkedList.add("db");
linkedList.add("dd");
linkedList.add("ll");
linkedList.add("l3");
int length = 0;
for (int i = 0; i < linkedList.size(); i++) {
length = i + 1;
}
if (length > 2) {
// 偶数
if (length % 2 == 0) {
int index = length / 2;
System.out.println("中间元素有:" + linkedList.get(index) + "," +
linkedList.get(index - 1));
}
// 奇数
if (length % 2 == 1){
int index = length / 2;
System.out.println("中间元素有:" + linkedList.get(index));
}
} else {
System.out.println("元素小于3个，没有中间元素");
}
}
二、快慢指针
思路如下：把一个链表看成一个跑道，fast 的速度是 slow 的两倍，那么当 fast 跑完全程后，slow 刚好跑一半，以此来达到找到中间节点的目的。
先创建链表结构，然后添加元素。(transient)Node节点：
transient Node last;
transient Node first;
private int length;
// node结构
public static class Node<T> {
// 数据
private T data;
// 上一个指针
private Node prev;
// 下一个指针
private Node next;
Node(Node prev, T data, Node next) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
// 链表添加操作
public void add(T data) {
final Node l = last;
final Node newNode = new Node(l, data, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
length++;
}
链表实现完毕就需要查找中间元素了：
public Node<T> getMiddleData(Node head) {
Node<T> fastNode = head;
while (fastNode.next != null) {
if (fastNode.next.next != null) {
head = head.next;
fastNode = fastNode.next.next;
} else {
head = head.next;
return head;
}
}
return head;
}
测试一下：
public static void main(String[] args) {
// null<---df<--->xxh<---db-->null
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("df"); //low next 1 xxh // fast next.next db
linkedList.add("xxh");
linkedList.add("db");
linkedList.add("xz");
linkedList.add("xz1");
Node<String> m=linkedList.getMiddleData(linkedList.first);
System.out.println(m.data);
}
