关于查找链表的中间元素

Question

我遵循以下方法来计算中间元素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

Answer 1

基本算法是

• 拿两个指针

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

• 首先使用两个节点递增,然后一次递增一个节点.

• 循环直到第一个循环到达结尾.此时,第二个将位于中间.

例:-

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

它肯定会在奇怪的情况下工作,因为即使你需要再检查一个条件,如果第一个点允许下一个移动而不是下一个接下来,那么两个指针都在中间你需要决定哪个作为中间.