关于查找链表的中间元素 [英] Regarding finding the middle element of linked list

问题描述

我按照以下方法计算链接列表中的中间元素，但我想要的是有任何内置方法或任何其他方法也可以找到同样容易，我所遵循的方法如下所示..

I am following the below approach to calculate the middle element from the linked list , but I want is there any built in method or any other approach which can also find the same easily , the approach that I am following is shown bellow..

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;
        }
    }
}

输出： -

Output:-

length of LinkedList: 4
middle element of LinkedList : 2

推荐答案

基本算法将是

• 拿两个指针

• Take two pointers

指向第一个节点

首先使用两个节点递增，然后一次递增一个。

Increment first with two nodes and second with one, at a time.

循环直到第一个循环到达结尾。此时，第二个将位于中间。

Loop until the 1st loop reaches the end. At this point, the 2nd will be at the middle.

示例： -

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

在奇数情况下肯定会有效，即使是情况你需要再检查一个条件，如果第一个点被允许移动下一个而不是下一个接下来那么两个指针都将位于中间你需要决定将哪个作为中间点。

It will definitely work in odd case, for even case you need to check one more condition if first point is allowed to move next but not next to next then both pointers will be at middle you need to decide which to take as middle.

这篇关于关于查找链表的中间元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！