5

我正在按照以下方法从 中计算中间元素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
4

5 回答 5

20

基本算法是

  • 拿两个指针

  • 使两者都指向第一个节点

  • 一次增加两个节点，第二个增加一个。

  • 循环直到第一个循环到达终点。此时，第二个将在中间。

例子：-

while ( p2.next != null ) {
    p2 = p2.next;
    if (p2.next != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
}

它肯定会在奇怪的情况下工作，即使在这种情况下，如果允许第一个点移动到下一个而不是下一个，那么您需要再检查一个条件，那么两个指针都将位于中间，您需要决定将哪个作为中间。

于 2013-02-20T08:48:47.283 回答
3

我建议使用内置的 Java

LinkedList<Object e>

它为您提供了所需的所有功能，例如获取长度：list.size()和中间对象：

list.get((list.size())/2);
于 2013-02-20T08:51:44.753 回答
2

选项：

  • 有一个双链表，同时从后面和前面走，直到你到达一个共同点。
  • 存储列表的大小，并在达到这个大小的一半时停止（类似于标准 APILinkedList所做的）。

除此之外，我认为你不能比你的算法做得更好。

于 2013-02-20T08:49:46.700 回答
1 
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);

进/出：5 10 15 25 35 25 40 出/出：25

于 2017-07-25T09:53:15.297 回答
0

这个问题的解决方案：

  • 使用两个索引first和second，都初始化为 0
  • 递增first1 和secondby2 * first
  • 将值设置first为中间
  • 循环将执行，直到值second小于列表大小

这是获取列表或链表的中间元素的代码片段：

private int getMiddle(LinkedList<String> list) {

   int middle = 0;
   int size = list.size();

   for (int i = 0, j = 0; j < size; j = i * 2) {
       middle = i++;
   }

   return middle;
}

LinkedList<String> 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));
于 2018-03-30T15:27:05.867 回答