在本教程中，我们将以最有效的方式讨论如何在LinkedList中找到中间元素。

假设：

我不在这里使用Java LinkedList API。
如果使用该API，则可以使用size()函数直接查找linkedlist的大小，然后定位长度/2.

算法之一：

• 遍历列表并找到列表的长度
• 查找长度后，再次遍历列表并从LinkedList的Head定位N/2元素。

时间复杂度=查找列表长度的时间+定位中间元素的时间= O(n)+ O(n)= o(n)空间复杂度= o(1)。

有效的方法：

上面的方法将需要两个遍历，但我们可以在一个遍历中找到中间元素也使用以下algo：

• 使用两个指针fastptr和stropptr并初始化链接列表头部
• 每次迭代中的一个节点将FastPtr移动到两个节点和慢动网。
• 当FastPtr到达节点的末尾时，慢动力指针将指向中间元素。

让我们为此创建Java程序：

package org.igi.theitroad;
/**
@author: igi Mandliya
*/
public class LinkedList{
 
	private Node head;
 
	private static class Node {
		private int value;
		private Node next;
 
		Node(int value) {
			this.value = value;
 
		}
	}
 
	public void addToTheLast(Node node) {
 
		if (head == null) {
			head = node;
		} else {
			Node temp = head;
			while (temp.next != null)
				temp = temp.next;
 
			temp.next = node;
		}
	}
 
 
	public void printList() {
		Node temp = head;
		while (temp != null) {
			System.out.format("%d ", temp.value);
			temp = temp.next;
		}
		System.out.println();
	}
 
	//This function will find middle element in linkedlist
	public Node findMiddleNode(Node head)
	{
		Node slowPointer, fastPointer; 
		slowPointer = fastPointer = head; 
 
		while(fastPointer !=null) { 
			fastPointer = fastPointer.next; 
			if(fastPointer != null && fastPointer.next != null) { 
				slowPointer = slowPointer.next; 
				fastPointer = fastPointer.next; 
			} 
		} 
 
		return slowPointer; 
 
	}
 
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		//Creating a linked list
		Node head=new Node(5);
		list.addToTheLast(head);
		list.addToTheLast(new Node(6));
		list.addToTheLast(new Node(7));
		list.addToTheLast(new Node(1));
		list.addToTheLast(new Node(2));
 
		list.printList();
		//finding middle element
		Node middle= list.findMiddleNode(head);
		System.out.println("Middle node will be: "+ middle.value);
 
	}
 
}

运行上面的程序，我们将获取以下输出：

5 6 7 1 2 
Middle node is: 7