java 查找链表中间元素_如何在Java中一次性查找Java中链表的中间元素
如何在一次傳遞中找到LinkedList的中間元素？這是一個 Java 和非Java程序員面試時經常被問到的編程問題。這個問題類似于檢查回文或計算階乘，有時也會要求編寫代碼。為了回答這個問題，候選人必須熟悉LinkedList的數據結構，即在單個LinkedList的情況下，鏈表的每個節點都包含數據和指針，這是下一個鏈表的地址，而單個鏈表的最后一個元素指向空值。因為要找到鏈接列表的中間元素，您需要找到LinkedList的長度，它將元素計數到末尾，即直到找到鏈接列表的最后一個元素為止。這個數據結構面試問題有趣的是，你需要一次找到LinkedList的中間元素，而你不知道LinkedList的長度。這就是應試者邏輯能力測試的地方，不管他是否熟悉時空權衡等。
你仔細想想你可以通過使用兩個指針來解決這個問題，如何在Java中查找單鏈表的長度。通過使用兩個指針，在每次迭代時遞增一個，在每次迭代時遞增另一個。當第一個指針指向鏈接列表的末尾時，第二個指針將指向鏈接列表的中間節點。
事實上，這兩個指針方法可以解決多個類似問題，例如如何在一次迭代中找到鏈接列表中最后一個的第三個元素或如何在鏈接列表中找到最后一個元素。在這個Java編程教程中，我們將看到一個Java程序，它在一次迭代中找到Linked List的中間元素。
Java程序在一次傳遞中查找LinkedList的中間元素
如何在Java中找到鏈表的中間元素，以Java為例，用Java程序找到鏈表中間節點。記住，LyKeDLead類是我們的自定義類，不要把這個類與JavaUTL.LIKEDLIST混淆，它是Java中一個流行的集合類。在這個Java程序中，我們的類鏈接表代表一個鏈表數據結構，它包含節點的集合并具有頭部和尾部。每個節點包含數據和地址部分。LIKEDListTestC類的主要方法用于模擬問題，在其中創建鏈表并在其中添加了幾個元素，然后在Java中對它們進行迭代，以一次傳遞中找到鏈接列表的中間元素。
import test.LinkedList.Node;
/**
* Java program to find middle element of linked list in one pass.
* In order to find middle element of linked list we need to find length first
* but since we can only traverse linked list one time, we will use two pointers
* one which we will increment on each iteration while other which will be
* incremented every second iteration. so when first pointer will point to the
* end of linked list, second will be pointing to the middle element of linked list
* @author
*/
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;
}
}
}
Output:
length of LinkedList: 4
middle element of LinkedList : 2
這就是如何在一次傳遞中找到LinkedList的中間元素。 ?此處提到的用于查找LinkedList的中間節點的技術也可用于從LinkedList中的Last或nth元素中找到第3個元素。
總結
以上是生活随笔為你收集整理的java 查找链表中间元素_如何在Java中一次性查找Java中链表的中间元素的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： oracle java_pool_siz
- 下一篇： java与jquery的选择器区别_ja