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

基本的なアルゴリズムは

  • 2 つのポインターを取る

  • 両方が最初のノードを指すようにする

  • 一度に 2 つのノードで最初にインクリメントし、次に 1 つのノードでインクリメントします。

  • 1 番目のループが最後に到達するまでループします。この時点で、2番目は真ん中になります。

例：-

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

偶数の場合、最初のポイントが次に移動することは許可されているが、次から次へ移動することは許可されていない場合は、もう 1 つの条件を確認する必要があります。

于 2013-02-20T08:48:47.283 に答える
3

組み込みのJavaを使用することをお勧めします

LinkedList<Object e>

list.size()length:や middle オブジェクトの取得など、必要なすべての機能が提供されます。

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

オプション:

  • 二重の連結リストを作成し、共通点に到達するまで前後に同時に進みます。
  • リストのサイズを保存し、この半分のサイズに達したら単純に停止します (標準 API の動作と同様LinkedList)。

それ以外は、アルゴリズムよりも優れているとは思いません。

于 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);

I/P:5 10 15 25 35 25 40 O/P:25

于 2017-07-25T09:53:15.297 に答える