java查找鏈表中間元素

您如何一次找到LinkedList的中間元素是一個編程問題，在電話采訪中經(jīng)常問Java和非Java程序員。 這個問題類似于檢查回文或
計算階乘 ，有時Interviewer還會要求編寫代碼。 為了回答這個問題，候選人必須熟悉LinkedList的數(shù)據(jù)結(jié)構(gòu)，即在單個LinkedList的情況下，Linked List的每個節(jié)點都包含數(shù)據(jù)和指針，這是下一個Linked List的地址，并且Singly Linked List的最后一個元素指向空值。 因為要找到鏈表的中間元素，您需要找到鏈表的長度，即計算元素的長度直到結(jié)束，即直到找到鏈表的最后一個元素。
是什么使得這個數(shù)據(jù)結(jié)構(gòu)面試問題有趣，是您需要找到inkedList的中間元素 一口氣 ，您不知道LinkedList的長度。

無論是否熟悉時空權(quán)衡等，這都是考生邏輯能力的考驗。

就像您仔細(xì)考慮過一樣，您可以使用兩個指針來解決此問題，如我上一篇有關(guān)如何在Java中查找單鏈接列表的長度的文章中所述 。

通過使用兩個指針，在每次迭代中增加一個指針，并在每第二次迭代中增加另一個指針。 當(dāng)?shù)谝粋€指針指向鏈接列表的末尾時，第二個指針將指向鏈接列表的中間節(jié)點。

實際上，這種兩指針方法可以解決多個類似的問題，例如
如何在一個迭代中從鏈表中的最后一個查找第三個節(jié)點，或如何從鏈表中的末個查找第N個元素。 在本Java編程教程中，我們將看到一個Java程序，該Java程序在一個迭代中找到“鏈表”的中間元素。

如何通過一遍查找LinkedList的中間元素

這是一個完整的Java程序，用于查找Java中“鏈表”的中間節(jié)點。 請記住，這里的LinkedList類是我們的自定義類，不要將該類與java.util.LinkedList混淆，該類是Java中流行的Collection類。

在此Java程序中，我們的類LinkedList表示一個鏈表數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)包含節(jié)點的集合并具有頭和尾。

每個節(jié)點包含數(shù)據(jù)和地址部分。 主要方法
LinkedListTest類用于模擬問題，我們在其中創(chuàng)建了鏈表，并在鏈表上添加了一些元素，然后對其進(jìn)行迭代以在Java中通過一次查找鏈表的中間元素。

import test.LinkedList.Node;/*** Java program to find middle element of linked list in one pass.* In order to find middle element of a linked list * we need to find the length first but since we can only * traverse linked list one time, we will have to use two pointers* one which we will increment on each iteration while * other which will be incremented every second iteration.* So when the first pointer will point to the end of a * linked list, second will be pointing to the middle * element of a linked list** @author Javin Paul*/ public class LinkedListTest {public static void main(String args[]) {//creating LinkedList with 5 elements including headLinkedList 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 passLinkedList.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中間節(jié)點的技術(shù)可用于從Last或
LinkedList中最后一個元素的第n個元素。

如果您喜歡這篇文章，并想嘗試一些更具挑戰(zhàn)性的編程練習(xí)，那么請看以下來自各種訪談的編程問題：

• 如何檢查LinkedList是否包含Java中的任何循環(huán)？ （ 解決方案 ）
• 如何在Java中搜索數(shù)組中的元素？ （ 解決方案 ）
• 如何使用冒泡排序算法對數(shù)組進(jìn)行排序？ （ 算法 ）
• 如何在Java中計算數(shù)字的總和？ （ 解決方案 ）
• 編寫程序來查找Java中String中的第一個非重復(fù)字符？ （ 程序 ）
• 如何檢查數(shù)字在Java中是否為二進(jìn)制？ （ 回答 ）
• 編寫程序以檢查數(shù)字是否為素數(shù)？ （ 解決方案 ）
• 如何防止Java死鎖？ （ 解決方案 ）
• 如何在Java中找到數(shù)字的最大素數(shù)？ （ 解決方案 ）
• 如何在Java中使用遞歸計算階乘？ （ 算法 ）
• 如何在Java中聲明和初始化二維數(shù)組？ （ 解決方案 ）
• 編寫一種方法來計算字符串中字符的出現(xiàn)次數(shù)？ （ 解決方案 ）
• 如何檢查號碼是否是阿姆斯特朗號碼？ （ 解決方案 ）
• 編寫一個程序，而不使用Collection API從數(shù)組中刪除重復(fù)項？ （ 程序 ）
• 如何在不使用API??方法的情況下反轉(zhuǎn)Java中的String？ （ 解決方案 ）
• 寫一個方法來從Java中的ArrayList中刪除重復(fù)項？ （ 解決方案 ）
• 編寫程序以檢查數(shù)字是否為回文？ （ 程序 ）
• 編寫程序以檢查數(shù)組是否包含重復(fù)的數(shù)字？ （ 解決方案 ）
• 如何找到不超過給定數(shù)字的斐波那契數(shù)列？ （ 解決方案 ）
• 編寫程序以查找排序數(shù)組中的缺失數(shù)字？ （ 算法 ）
• 關(guān)于Java數(shù)組有10點？ （ 必須知道事實 ）
• 如何在Java中找到整數(shù)數(shù)組的前兩個最大值？ （ 解決方案 ）
• 編寫一種方法來檢查兩個String是否是彼此的Anagram？ （ 方法 ）
• 如何找到數(shù)組中最大和最小的數(shù)字？ （ 解決方案 ）
• 編寫函數(shù)一次找到鏈接列表的中間元素？ （ 解決方案 ）
• 如何解決Java中的生產(chǎn)者－消費者問題。 （ 解決方案 ）
• 編寫程序以檢查數(shù)字是否為2的冪？ （ 程序 ）

到目前為止，感謝您閱讀此編碼面試問題。 如果您喜歡這個String面試問題，請與您的朋友和同事分享。 如果您有任何問題或反饋，請發(fā)表評論。

翻譯自: https://www.javacodegeeks.com/2019/03/middle-element-linked-list-java-single-pass.html

java查找鏈表中間元素

總結(jié)

以上是生活随笔為你收集整理的java查找链表中间元素_如何通过Java单次查找链表的中间元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。