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:
- Program for n'te node fra slutningen af en linket liste
- Find midten af en given linket listedatastruktur
- Indsættelse af en ny node i en linket listedatastruktur
- Find længden af en linket listedatastruktur (iterativ og rekursiv)