Java >> Java tutorial >  >> Java

Java-program til at vende en sammenkædet liste i par

I denne tutorial vil vi se, hvordan man vender en sammenkædet liste i par i java. LinkedList er en lineær datastruktur, hvor elementerne ikke er gemt på sammenhængende steder, og hvert element er et separat objekt med en datadel og adressedel. Hvert element er kendt som en node. På grund af dynamikken og lette indsættelser og sletninger foretrækkes de frem for arrays. Men før du går videre, hvis du ikke er bekendt med konceptet med den linkede liste i java, så tjek artiklen om Linked List i Java.

Input: Indtast Linked List-elementerne:6 7 8 4 5 3

Output: Før du vender tilbage til den linkede liste:6 7 8 9 5

Efter at have vendt den linkede liste:7 6 9 8 3 5

Dette kan gøres ved at bruge følgende metoder:

Fremgangsmåde 1:Ved iteration

Fremgangsmåde 2:Ved rekursion

Lad os se på hver af disse tilgange for en bedre forståelse.

Program 1:Java-program til at vende en sammenkædet liste i par

I dette program vil vi se, hvordan man vender en sammenkædet liste i par i java ved at bruge den iterative tilgang.

Algorithme:

  1. Start
  2. Deklarer en sammenkædet liste over heltalstyper uden nogen initial størrelse.
  3. Brug add-metoden til at tilføje elementerne.
  4. Tilføj elementerne i slutningen af ​​listen.
  5. Udskriv de linkede listeelementer, før du vender tilbage.
  6. Forbind først to noder korrekt, og skift derefter disse noder.
  7. Da det forrige link er brudt, skal du nu igen forbinde noderne.
  8. Udskriv de sammenkædede listeelementer efter omvendt.
  9. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

//Java Program to Reverse a linked list in Pairs
public class ReverseLinkedListInPair
{
    private Node head;
    private static class Node 
    {
        private int value;
        private Node next;
        Node(int value) {
            this.value = value;
        }
    }
    public void addLast(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
    }
    public void printLinkedList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
    // Reverse the linked list in pair
    public static Node reverseLLInPairs(Node head) 
    {
        Node current=head;
        Node temp=null;
        Node newHead =null;
        while (current != null && current.next != null) 
        {
            if (temp != null) 
            {
                temp.next.next = current.next;
            }
            temp=current.next;     
            current.next=temp.next;
            temp.next=current;
            if (newHead == null)
                newHead = temp;
            current=current.next;
        }     
        return newHead;
    }
    //Driver Code
    public static void main(String[] args) {
        ReverseLinkedListInPair li = new ReverseLinkedListInPair();
        // Creating a linked list
        Node head=new Node(0);
        li.addLast(head);
        li.addLast(new Node(1));
        li.addLast(new Node(2));
        li.addLast(new Node(3));
        li.addLast(new Node(4));
        li.addLast(new Node(5));
        System.out.println("Before reversing in pair: ");
        li.printLinkedList(head);
        //Reversing LinkedList in pairs
        Node result=reverseLLInPairs(head);
        System.out.println("After reversing in pair: ");
        li.printLinkedList(result);
    }
}


Før vending i par:
0 1 2 3 4 5
Efter vending i par:
1 0 3 2 5 4

Program 2:Java-program til at vende den linkede liste i par

I dette program vil vi se, hvordan man vender en sammenkædet liste i par i java ved at bruge den rekursive tilgang.

Algorithme:

  1. Start
  2. Deklarer en sammenkædet liste over heltalstyper uden nogen initial størrelse.
  3. Brug add-metoden til at tilføje elementerne.
  4. Tilføj elementerne i slutningen af ​​listen.
  5. Udskriv de linkede listeelementer, før du vender tilbage.
  6. Forbind først to noder korrekt, og kald derefter den rekursive funktion for at bytte elementerne.
  7. Da det forrige link er brudt, skal du nu igen forbinde noderne.
  8. Udskriv de sammenkædede listeelementer efter omvendt.
  9. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

//Java Program to Reverse a linked list in Pairs
public class ReverseLinkedListInPair
{
    private Node head;
    private static class Node 
    {
        private int value;
        private Node next;
        Node(int value) {
            this.value = value;
        }
    }
    public void addLast(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
    }
    public void printLinkedList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
    // Reverse the linked list in pair
    public static Node reverseLLInPairs(Node head) 
    {
        if (head == null || head.next == null) {
          return head;
      }
      Node temp=head.next;
      head.next=temp.next;
      temp.next=head;
      head.next=reverseLLInPairs(head.next);
      return temp;
    }
    //Driver Code
    public static void main(String[] args) {
        ReverseLinkedListInPair li = new ReverseLinkedListInPair();
        // Creating a linked list
        Node head=new Node(0);
        li.addLast(head);
        li.addLast(new Node(1));
        li.addLast(new Node(2));
        li.addLast(new Node(3));
        li.addLast(new Node(4));
        li.addLast(new Node(5));
        System.out.println("Before reversing in pair: ");
        li.printLinkedList(head);
        //Reversing LinkedList in pairs
        Node result=reverseLLInPairs(head);
        System.out.println("After reversing in pair: ");
        li.printLinkedList(result);
    }
}


Før vending i par:
0 1 2 3 4 5
Efter vending i par:
1 0 3 2 5 4


Java tag