关于查找链表的中间元素
我遵循以下方法来计算linked list的中间元素，但我想要的是有任何内置方法或任何其他方法也可以轻松找到相同的方法，我所遵循的方法如下所示：
import test.LinkedList.Node; public class LinkedListTest { public static void main(String args[]) { //creating LinkedList with 5 elements including head LinkedList linkedList = new LinkedList(); LinkedList.Node head = linkedList.head(); linkedList.add( new LinkedList.Node("1")); linkedList.add( new LinkedList.Node("2")); linkedList.add( new LinkedList.Node("3")); linkedList.add( new LinkedList.Node("4")); //finding middle element of LinkedList in single pass LinkedList.Node current = head; int length = 0; LinkedList.Node middle = head; while(current.next() != null){ length++; if(length%2 ==0){ middle = middle.next(); } current = current.next(); } if(length%2 == 1){ middle = middle.next(); } System.out.println("length of LinkedList: " + length); System.out.println("middle element of LinkedList : " + middle); } } class LinkedList{ private Node head; private Node tail; public LinkedList(){ this.head = new Node("head"); tail = head; } public Node head(){ return head; } public void add(Node node){ tail.next = node; tail = node; } public static class Node{ private Node next; private String data; public Node(String data){ this.data = data; } public String data() { return data; } public void setData(String data) { this.data = data; } public Node next() { return next; } public void setNext(Node next) { this.next = next; } public String toString(){ return this.data; } } }
输出： –
length of LinkedList: 4 middle element of LinkedList : 2
基本算法是
-
拿两个指针
-
使两者都指向第一个节点
-
首先增加两个节点，然后一个增加一个节点。
-
循环直到第一个循环到达结尾。 此时，第二个将位于中间。
例：-
while ( p2.next != null ) { p2 = p2.next; if (p2.next != null) { p2 = p2.next; p1 = p1.next; } }
它肯定会在奇怪的情况下工作，因为即使你需要再检查一个条件，如果第一个点允许下一个移动而不是下一个接下来，那么两个指针都将位于中间，你需要决定将哪个作为中间。
选项：
- 有一个双链表，同时从后面和前面走，直到你达到共同点。
- 存储列表的大小，并在达到此大小的一半时停止（类似于标准API的
LinkedList所做的那样）。
除此之外，我认为你不能比你的算法做得更好。
我建议使用内置的Java
LinkedList
它为您提供了获取长度所需的所有function： list.size()和中间对象：
list.get((list.size())/2);
public Node getMiddleElement(Node head) { Node slow_pointer=head; Node fast_pointer=head; while(fast_pointer.next!=null && fast_pointer.next.next!=null) { slow_pointer=slow_pointer.next; fast_pointer=fast_pointer.next.next; } return slow_pointer; } Node mid_elem=PrintMiddleElement(head); System.out.println(mid_elem.data);
I / P：5 10 15 25 35 25 40 O / P：25
这个问题的解决方案：
- 使用两个索引，
first和second，都初始化为0 -
first增加1，然后增加2 * first - 设置
first到中间的值 - 循环将执行，直到
second值小于列表大小
这是获取列表或链表的中间元素的代码片段：
private int getMiddle(LinkedList list) { int middle = 0; int size = list.size(); for (int i = 0, j = 0; j < size; j = i * 2) { middle = i++; } return middle; } LinkedList list = new LinkedList<>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); list.add("6"); list.add("7"); int middle = getMiddle(list); System.out.println(list.get(middle));