Java >> Java tutorial >  >> Java

Find midten af ​​en given linket listedatastruktur

Spørgsmål:I givet en linket liste skal du finde midten af ​​listen og udskrive nummeret.

Indgang:-> 4-> 2-> 7-> 9-> 1

Udgang:7

Før du starter, skal du kende til Linked List og hvordan man opretter den og Indsættelse af node (data) i LinkedList.

Der er mange tilgange til at finde mellemtal i LinkedList.

1. Single pointer tilgang

I denne tilgang vil vi scanne hele listen og tælle antallet af noder. Vi dividerer tallet med 2 og krydser så igen listen op til den node.

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);

            Node pointerNode = head;
            int countNodes = 0;
            while (countNodes != middleNode -1) {
                pointerNode = pointerNode.next;
                countNodes ++;
            }
            System.out.println("\nMiddle node of linked List is " + middleNode);
            System.out.println("Middle node data is " + pointerNode.data);
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findMiddleNode();
    }
}

Udgang:-> 4-> 2-> 7-> 9-> 1
Midterste knude på linket liste er 3
Midterste node data er 7

Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)
Space Complexity: O(1)

2. Brug af 2 pointere

Med 2 pointere til at krydse listen, kan vi finde midten af ​​listen med kun én scanning på den linkede liste.

  • pointer1 rejser én node ad gangen
  • pointe2 rejser to noder ad gangen.

Således, når pointe2 når slutningen af ​​den linkede liste, pointer1 vil pege på midten af ​​den linkede liste.

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            Node pointer1 = head;
            Node pointer2 = head;

            while (pointer2 != null && pointer2.next != null) {
                pointer1 = pointer1.next;
                pointer2 = pointer2.next.next;
            }
            System.out.println("\nMiddle node data is " + pointer1.data);
        }
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findMiddleNode();
    }
}

Output: -> 4-> 2-> 7-> 9-> 1
Midterste node data er 7

Time Complexity: O(n)
Space Complexity: O(1)

her er flere LinkedList-interviewspørgsmål :

  1. Program til at finde n'te node fra slutningen af ​​en linket liste
  2. Reversere en linket listedatastruktur i java
  3. Indsættelse af en ny node i en linket listedatastruktur
  4. Find længden af ​​en linket listedatastruktur (iterativ og rekursiv)

Java tag