Java >> Java tutorial >  >> Java

Vend en linket listedatastruktur i java

Linket liste eller Singly Linked List er en type datastruktur. På en  linket liste , hver node gemmer indholdet og en pointer (reference) for den næste node. Omvendt en linket liste er vigtigt for at forstå fleksibiliteten og anvendeligheden af ​​linket liste.

Spørgsmål:

Givet markøren til hovedknuden på en linket liste, er opgaven at vende den linkede liste. Du skal vende listen ved at ændre links mellem noder.

Eksempel:

Givet linket liste:-> 4-> 2-> 7-> 9-> 1
Omvendt linket liste:-> 1-> 9-> 7-> 2-> 4

Løsninger: Iterativ metode

1. Initialiser tre pointere

currentNode = head; nextNode = null; previousNode = null;

2. Gentag gennem den linkede liste. Gør følgende i while-løkken.

//store næste node
currentNode = currentNode->nextNode

// Vend nodemarkører

currentNode -> next = previousNode 

// Flyt forrige og nuværende node et skridt frem
previousNode = currentNode
currentNode = nextNode

Fuldført kode :

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 reverseLinkedList() {

        Node currentNode = head;
        Node nextNode = null;
        Node previousNode = null;
        while (currentNode !=null){
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        head = previousNode;
        printAllNodes("\nReverse Linked list : ");
    }

    void printAllNodes(String mesg) {
        Node node = head;
        System.out.print(mesg);
        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("Given Linked list : ");
        linkedList.reverseLinkedList();
    }
}

Tidskompleksitet: O(n)
Rumkompleksitet: O(1)

Omvendt en linket liste er øverst på listen over java-interviewspørgsmål, så øv dig mere... her er flere LinkedList-interviewspørgsmål:

  1. Program for n'te node fra slutningen af ​​en linket liste
  2. Find midten af ​​en given linket listedatastruktur
  3. Indsættelse af en ny node i en linket listedatastruktur
  4. Find længden af ​​en linket listedatastruktur (iterativ og rekursiv)

Java tag