转载

如何在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中对它们进行迭代，以一次传递中找到链接列表的中间元素。

<b>import</b> test.LinkedList.Node;

<font><i>/**
 * 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
 */</i></font><font>
<b>public</b> <b>class</b> LinkedListTest {
  
  
    <b>public</b> <b>static</b> <b>void</b> main(String args[]) {
        </font><font><i>//creating LinkedList with 5 elements including head</i></font><font>
      LinkedList linkedList = <b>new</b> LinkedList();
      LinkedList.Node head = linkedList.head();
      linkedList.add( <b>new</b> LinkedList.Node(</font><font>"1"</font><font>));
      linkedList.add( <b>new</b> LinkedList.Node(</font><font>"2"</font><font>));
      linkedList.add( <b>new</b> LinkedList.Node(</font><font>"3"</font><font>));
      linkedList.add( <b>new</b> LinkedList.Node(</font><font>"4"</font><font>));
    
      </font><font><i>//finding middle element of LinkedList in single pass</i></font><font>
      LinkedList.Node current = head;
      <b>int</b> length = 0;
      LinkedList.Node middle = head;
    
      <b>while</b>(current.next() != <b>null</b>){
          length++;
          <b>if</b>(length%2 ==0){
              middle = middle.next();
          }
          current = current.next();
      }
    
      <b>if</b>(length%2 == 1){
          middle = middle.next();
      }

      System.out.println(</font><font>"length of LinkedList: "</font><font> + length);
      System.out.println(</font><font>"middle element of LinkedList : "</font><font> + middle);
      
    } 
  
}

<b>class</b> LinkedList{
    <b>private</b> Node head;
    <b>private</b> Node tail;
  
    <b>public</b> LinkedList(){
        <b>this</b>.head = <b>new</b> Node(</font><font>"head"</font><font>);
        tail = head;
    }
  
    <b>public</b> Node head(){
        <b>return</b> head;
    }
  
    <b>public</b> <b>void</b> add(Node node){
        tail.next = node;
        tail = node;
    }
  
    <b>public</b> <b>static</b> <b>class</b> Node{
        <b>private</b> Node next;
        <b>private</b> String data;

        <b>public</b> Node(String data){
            <b>this</b>.data = data;
        }
      
        <b>public</b> String data() {
            <b>return</b> data;
        }

        <b>public</b> <b>void</b> setData(String data) {
            <b>this</b>.data = data;
        }

        <b>public</b> Node next() {
            <b>return</b> next;
        }

        <b>public</b> <b>void</b> setNext(Node next) {
            <b>this</b>.next = next;
        }
      
        <b>public</b> String toString(){
            <b>return</b> <b>this</b>.data;
        }
    }
}

Output:
length of LinkedList: 4
middle element of LinkedList : 2
</font>

这就是如何在一次传递中找到LinkedList的中间元素。此处提到的用于查找LinkedList的中间节点的技术也可用于从LinkedList中的Last或nth元素中找到第3个元素。

原文 https://www.jdon.com/51589

正文到此结束