Reverse Singlelink List Java

Kann mir jemand sagen, warum mein code dosent Arbeit? Ich will umkehren, eine einfach verkettete Liste in java: Dies ist die Methode (funktioniert nicht richtig)

public void reverseList(){
    Node before = null;
    Node tmp = head;
    Node next = tmp.next;
    while(tmp != null){
      if(next == null)
         return;
      tmp.next = before;
      before = tmp;
      tmp = next;
      next = next.next;
    }
}

- Und das ist die Knoten-Klasse:

public class Node{
   public int data;
   public Node next;
   public Node(int data, Node next){
      this.data = data;
      this.next = next;
   }
}

Auf Eingang 4->3->2->1 ich habe Ausgabe 4. Ich gedebuggt und es setzt Pointer korrekt, aber trotzdem habe ich nicht bekommen, warum gibt es nur 4.

InformationsquelleAutor der Frage sammy333 | 2014-03-24

java singly-linked-list

Node next = tmp.next;
while(tmp != null){

Also, was passiert, wenn tmp == null?

Sie hat es fast, aber.

Node before = null;
Node tmp = head;
while (tmp != null) {
    Node next = tmp.next;
    tmp.next = before;
    before = tmp;
    tmp = next;
}
head = before;

Oder in schöner (?) Benennung:

Node reversedPart = null;
Node current = head;
while (current != null) {
    Node next = current.next;
    current.next = reversedPart;
    reversedPart = current;
    current = next;
}
head = reversedPart;

ASCII-Kunst:

        <__<__<__ __ : reversedPart    : head
                 (__)__ __ __
head :   current:      >  >  >

InformationsquelleAutor der Antwort Joop Eggen

public Node<E> reverseList(Node<E> node) {
    if (node == null || node.next == null) {
        return node;
    }
    Node<E> currentNode = node;
    Node<E> previousNode = null;
    Node<E> nextNode = null;

    while (currentNode != null) {
        nextNode = currentNode.next;
        currentNode.next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;
    }
    return previousNode;
}

InformationsquelleAutor der Antwort Ranjeet

Die Methode für die Umkehrung einer verknüpften Liste ist, wie unten;

Reverse-Methode

public void reverseList() {
    Node<E> curr = head;
    Node<E> pre = null;
    Node<E> incoming = null;

    while(curr != null) {
        incoming = curr.next;   //store incoming item

        curr.next = pre;        //swap nodes
        pre = curr;             //increment also pre

        curr = incoming;        //increment current
    }

    head = pre; //pre is the latest item where
                //curr is null
}

Drei Referenzen sind erforderlich, um das umkehren einer Liste: precurreingehende

...      pre     curr    incoming
... --> (n-1) --> (n) --> (n+1) --> ...

Umkehren einen Knoten, den Sie haben, zu speichern prePrevious element, so dass Sie verwenden können, die einfache stament;

curr.next = pre;

Umkehr des aktuellen Elements in der Richtung. Jedoch Durchlaufen Sie die Liste, die Sie haben, zu speichern eingehende element vor der Ausführung der Anweisung oben, weil, wie die Umkehrung des aktuellen Elements nächste Referenz, die Sie nicht wissen, die eingehende element mehr, das ist, warum eine Dritte Referenz benötigt.

Den demo-code ist wie folgt;

LinkedList-Beispiel Klasse

public class LinkedList<E> {

    protected Node<E> head;

    public LinkedList() {
        head = null;
    }

    public LinkedList(E[] list) {
        this();
        addAll(list);
    }

    public void addAll(E[] list) {
        for(int i = 0; i < list.length; i++)
            add(list[i]);
    }

    public void add(E e) {
        if(head == null)
            head = new Node<E>(e);
        else {
            Node<E> temp = head;

            while(temp.next != null)
                temp = temp.next;

            temp.next = new Node<E>(e);
        }
    }

    public void reverseList() {
        Node<E> curr = head;
        Node<E> pre = null;
        Node<E> incoming = null;

        while(curr != null) {
            incoming = curr.next;   //store incoming item

            curr.next = pre;        //swap nodes
            pre = curr;             //increment also pre

            curr = incoming;        //increment current
        }

        head = pre; //pre is the latest item where
                    //curr is null
    }

    public void printList() {
        Node<E> temp = head;

        System.out.print("List: ");
        while(temp != null) {
            System.out.print(temp + " ");
            temp = temp.next;
        }

        System.out.println();
    }

    public static class Node<E> {

        protected E e;
        protected Node<E> next;

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }

    }

}

Test-Code

public class ReverseLinkedList {

    public static void main(String[] args) {
        Integer[] list = { 4, 3, 2, 1 };

        LinkedList<Integer> linkedList = new LinkedList<Integer>(list);

        linkedList.printList();
        linkedList.reverseList();
        linkedList.printList();
    }

}

Ausgabe

List: 4 3 2 1 
List: 1 2 3 4

InformationsquelleAutor der Antwort Levent Divilioglu

6

Wenn das nicht Hausaufgaben machen, und Sie tun dies "manuell" über Zweck, dann würde ich empfehlen, mit
```
Collections.reverse(list);
```
Sammlungen.reverse() gibt void zurück, und Ihre Liste ist Umgekehrt, nachdem Sie den Anruf.

InformationsquelleAutor der Antwort Oliver Hausler

Wir haben drei Knoten vorherigen,aktuellen und nächsten.

public void reverseLinkedlist()
{
    /*
     * Have three nodes i.e previousNode,currentNode and nextNode
 When currentNode is starting node, then previousNode will be null
 Assign currentNode.next to previousNode to reverse the link.
 In each iteration move currentNode and previousNode by  1 node.
     */

    Node previousNode = null;
    Node currentNode = head;
    while (currentNode != null) 
    {
        Node nextNode = currentNode.next;
        currentNode.next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;
    }
    head = previousNode;
}

InformationsquelleAutor der Antwort Sathesh Balakrishnan Manohar

public void reverse() {
    Node prev = null; Node current = head; Node next = current.next;
    while(current.next != null) {
        current.next = prev;
        prev = current;
        current = next;
        next = current.next;
    }
    current.next = prev;
    head = current;
}

InformationsquelleAutor der Antwort Sean Paul

Kenne ich die rekursive Lösung ist nicht optimal, aber wollte nur hinzufügen, hier:

public class LinkedListDemo {

    static class Node {
        int val;
        Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public static void main(String[] args) {
        Node n = new Node(1, new Node(2, new Node(3, new Node(20, null))));
        display(n);
        n = reverse(n);
        display(n);
    }

    static Node reverse(Node n) {
        Node tail = n;
        while (tail.next != null) {
            tail = tail.next;
        }
        reverseHelper(n);
        return (tail);
    }

    static Node reverseHelper(Node n) {
        if (n.next != null) {
            Node reverse = reverseHelper(n.next);
            reverse.next = n;
            n.next = null;
            return (n);
        }
        return (n);
    }

    static void display(Node n) {
        for (; n != null; n = n.next) {
            System.out.println(n);
        }
    }
}

InformationsquelleAutor der Antwort Jose Cifuentes

Ich verstehe es nicht... warum nicht, dies zu tun :

private LinkedList reverseLinkedList(LinkedList originalList){
    LinkedList reversedList = new LinkedList<>();

    for(int i=0 ; i<originalList.size() ; i++){
        reversedList.add(0, originalList.get(i));
    }

    return reversedList;
}

Ich finde das einfacher.

InformationsquelleAutor der Antwort Manov

Eine elegantere Lösung wäre die Verwendung von Rekursion

void ReverseList(ListNode current, ListNode previous) {
            if(current.Next != null) 
            {
                ReverseList(current.Next, current);
                ListNode temp = current.Next;
                temp.Next = current;
                current.Next = previous;
            }
        }

InformationsquelleAutor der Antwort Shayno

Node reverse_rec(Node start) {
    if (start == null || start -> next == null) {
       return start;
   }

   Node new_start = reverse(start->next);
   start->next->next = start;
   start->next = null;
   return new_start;
}


Node reverse(Node start) {
    Node cur = start;
    Node bef = null;

    while (cur != null) {
       Node nex = cur.next;
       cur.next = bef;
       bef = cur;
       cur = nex;
   }
   return bef;

}

InformationsquelleAutor der Antwort user2547616

1

Habe ich versucht den folgenden code und es funktioniert gut:
```
Node head = firstNode;
Node current = head;
while(current != null && current.next != null){
    Node temp = current.next;
    current.next = temp.next;
    temp.next = head;
    head = temp;
}
```
Im Grunde genommen eins nach dem anderen setzt es die nächste Zeiger von einem Knoten zum nächsten, zum nächsten Knoten, so dass vom nächsten ab alle Knoten sind mit an der Rückseite der Liste.

InformationsquelleAutor der Antwort shailendra1118
0

Ich glaube, dein problem ist, dass Ihr zunächst letztes element nächsten Attribut nicht geändert werden, weil von Ihrem Zustand
```
if(next == null)
     return;
```
Ist am Anfang der Schleife.

Ich würde es verschieben, direkt nach tmp.nächste zugewiesen wurde:
```
while(tmp != null){

  tmp.next = before;
  if(next == null)
     return;
  before = tmp;
  tmp = next;
  next = next.next;
}
```
InformationsquelleAutor der Antwort Pablo Francisco Pérez Hidalgo

Verwenden.

if (current== null || current.next==null) return current;
 Node nextItem = current.next;
 current.next = null;
 Node reverseRest = reverse(nextItem);
 nextItem.next = current;
 return reverseRest

oder Java-Programm zu reverse-eine Einfach Verknüpfte Liste

InformationsquelleAutor der Antwort Shriram

package com.three;

public class Link {

    int a;
    Link Next;

    public Link(int i){
        a=i;
    }

}

public class LinkList {

    Link First = null;

    public void insertFirst(int a){
        Link objLink = new Link(a);

        objLink.Next=First;
        First = objLink;

    }

    public void displayLink(){

        Link current = First;
        while(current!=null){
            System.out.println(current.a);
            current = current.Next;
        }

    }

    public void ReverseLink(){
        Link current = First;
        Link Previous = null;
        Link temp = null;

        while(current!=null){

            if(current==First)
                temp = current.Next;
            else
                temp=current.Next;

            if(temp==null){
                First = current;
                //return;
            }
            current.Next=Previous;
            Previous=current;
            //System.out.println(Previous);
            current = temp;
        }

    }

    public static void main(String args[]){

        LinkList objLinkList = new LinkList();
        objLinkList.insertFirst(1);
        objLinkList.insertFirst(2);
        objLinkList.insertFirst(3);
        objLinkList.insertFirst(4);
        objLinkList.insertFirst(5);
        objLinkList.insertFirst(6);
        objLinkList.insertFirst(7);
        objLinkList.insertFirst(8);
        objLinkList.displayLink();
        System.out.println("-----------------------------");
        objLinkList.ReverseLink();
        objLinkList.displayLink();

    }

}

InformationsquelleAutor der Antwort prashant chaudhary

Können Sie auch versuchen, diese

    LinkedListNode pointer = head;
    LinkedListNode prev = null, curr = null;

    /* Pointer variable loops through the LL */
    while(pointer != null)
    {
        /* Proceed the pointer variable. Before that, store the current pointer. */
        curr = pointer; //         
        pointer = pointer.next;         

        /* Reverse the link */
        curr.next = prev;

        /* Current becomes previous for the next iteration */
        prev = curr;            
    }

    System.out.println(prev.printForward());

InformationsquelleAutor der Antwort Sankalp

public class SinglyLinkedListImpl {

private Node<T> head;

public void add(T element) {
    Node<T> item = new Node<T>(element);
    if (head == null) {
        head = item;
    } else {
        Node<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = item;
    }
}

private void reverse() {

    Node<T> temp = null;
    Node<T> next = null;
    while (head != null) {
        next = head.next;
        head.next = temp;
        temp = head;
        head = next;
    }
    head = temp;
}

void printList(Node<T> node) {
    while (node != null) {
        System.out.print(node.data + " ");
        node = node.next;
    }
    System.out.println();
}

public static void main(String a[]) {
    SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();
    sl.add(1);
    sl.add(2);
    sl.add(3);
    sl.add(4);

    sl.printList(sl.head);
    sl.reverse();
    sl.printList(sl.head);

}

static class Node<T> {

    private T data;
    private Node<T> next;

    public Node(T data) {
        super();
        this.data = data;
    }

}

}

InformationsquelleAutor der Antwort Shivanshu

package LinkedList;

import java.util.LinkedList;

public class LinkedListNode {

    private int value;
    private LinkedListNode next = null;

    public LinkedListNode(int i) {
        this.value = i;
    }

    public LinkedListNode addNode(int i) {
        this.next = new LinkedListNode(i);
        return next;
    }

    public LinkedListNode getNext() {
        return next;
    }

    @Override
    public String toString() {
        String restElement = value+"->";
        LinkedListNode newNext = getNext();
        while(newNext != null)
            {restElement = restElement + newNext.value + "->";
            newNext = newNext.getNext();}
        restElement = restElement +newNext;
        return restElement;
    }

    public static void main(String[] args) {
        LinkedListNode headnode = new LinkedListNode(1);
        headnode.addNode(2).addNode(3).addNode(4).addNode(5).addNode(6);

        System.out.println(headnode);
        headnode = reverse(null,headnode,headnode.getNext());

        System.out.println(headnode);
    }

    private static LinkedListNode reverse(LinkedListNode prev, LinkedListNode current, LinkedListNode next) {
        current.setNext(prev);
        if(next == null)
            return current;
         return reverse(current,next,next.getNext());   
    }

    private void setNext(LinkedListNode prev) {
        this.next = prev;
    }
}

InformationsquelleAutor der Antwort user5807826

public class ReverseLinkedList {

    public static void main(String args[]){
        LinkedList<String> linkedList = new LinkedList<String>();
        linkedList.add("a");
        linkedList.add("b");
        linkedList.add("c");
        linkedList.add("d");
        linkedList.add("e");
        linkedList.add("f");
        System.out.println("Original linkedList:");
        for(int i = 0; i <=linkedList.size()-1; i++){

            System.out.println(" - "+ linkedList.get(i));

        }
        LinkedList<String> reversedlinkedList = reverse(linkedList);
        System.out.println("Reversed linkedList:");
        for(int i = 0; i <=reversedlinkedList.size()-1; i++){
            System.out.println(" - "+ reversedlinkedList.get(i));

        }
    }

    public static LinkedList<String> reverse(LinkedList<String> linkedList){

        for(int i = 0; i < linkedList.size()/2; i++){
            String temp = linkedList.get(i);
            linkedList.set(i, linkedList.get(linkedList.size()-1-i));
            linkedList.set((linkedList.size()-1-i), temp);
        }
        return linkedList;
    }
}

InformationsquelleAutor der Antwort Armaan Singh Sekhon

Umkehren eine einfach verknüpfte Liste, die Sie sollten drei Knoten, topbeforeTop und AfterTop. Oben ist der header einfach verkettete Liste, daher beforeTop wäre null und afterTop wäre nächste element top und mit jeder iteration vorwärts beforeTop zugeordnet ist top und top zugeordnet ist afterTop(d.h. top.neben).

private static Node inverse(Node top) {
        Node beforeTop=null, afterTop;
        while(top!=null){
            afterTop=top.next;
            top.next=beforeTop;
            beforeTop=top;
            top=afterTop;
        }
        return beforeTop;
    }

InformationsquelleAutor der Antwort bpjoshi

Mit Rekursion ist Es zu einfach :

package com.config;

import java.util.Scanner;

public class Help {

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        Node head = null;
        Node temp = null;
        int choice = 0;
        boolean flage = true;
        do{
            Node node = new Node();
            System.out.println("Enter Node");
            node.data = sc.nextInt();
            if(flage){
                head = node;
                flage = false;
            }
            if(temp!=null)
                temp.next = node;
            temp = node;

            System.out.println("Enter 0 to exit.");
            choice = sc.nextInt();
        }while(choice!=0);

        Help.getAll(head);

        Node reverse = Help.reverse(head,null);
        //reverse = Help.reverse(head, null);

        Help.getAll(reverse);

    }

    public static void getAll(Node head){
        if(head==null)
            return ;
        System.out.println(head.data+"Memory Add "+head.hashCode());
        getAll(head.next);
    }

    public static Node reverse(Node head,Node tail){
        Node next = head.next;
        head.next = tail;
        return (next!=null? reverse(next,head) : head);
    }
}

class Node{
    int data = 0;
    Node next = null;
}

InformationsquelleAutor der Antwort ritesh9984

    //Java program for reversing the linked list
    class LinkedList {

        static Node head;

        static class Node {

            int data;
            Node next;

            Node(int d) {
                data = d;
                next = null;
            }
        }

      // Function to reverse the linked list 
        Node reverse(Node node) {
            Node prev = null;
            Node current = node;
            Node next = null;
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            node = prev;
            return node;
        }




        //prints content of double linked list
        void printList(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }


        public static void main(String[] args) {
            LinkedList list = new LinkedList();
            list.head = new Node(85);
            list.head.next = new Node(15);
            list.head.next.next = new Node(4);
            list.head.next.next.next = new Node(20);

            System.out.println("Given Linked list");
            list.printList(head);
            head = list.reverse(head);
            System.out.println("");
            System.out.println("Reversed linked list ");
            list.printList(head);
        }
    }


OUTPUT: -

Given Linked list
85 15 4 20 
Reversed linked list 
20 4 15 85

InformationsquelleAutor der Antwort saurabh prakash

Node Reverse(Node head) {
        Node n,rev;
        rev = new Node();
        rev.data = head.data;
        rev.next = null;


        while(head.next != null){
            n = new Node();
            head = head.next;
            n.data = head.data;
            n.next = rev;
            rev = n;
            n=null;


        }
    return rev;
}

Verwenden Sie obige Funktion rückgängig einfach verkettete Liste.

InformationsquelleAutor der Antwort Aditya Parmar

 public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

prüfen Sie weitere details über die Komplexität der Analyse
http://javamicro.com/ref-card/DS-Algo/How-to-Reverse-Singly-Linked-List?

InformationsquelleAutor der Antwort jitendra

public static LinkedList reverseLinkedList(LinkedList node) {
    if (node == null || node.getNext() == null) {
        return node;
    }

    LinkedList remaining = reverseLinkedList(node.getNext());
    node.getNext().setNext(node);
    node.setNext(null);
    return remaining;
}

InformationsquelleAutor der Antwort Aman

/**
 * Reverse LinkedList
 * @author asharda
 *
 */

class Node
{
  int data;
  Node next;
  Node(int data)
  {
    this.data=data;
  }
}
public class ReverseLinkedList {

  static Node root;
  Node temp=null;
  public void insert(int data)
  {
    if(root==null)
    {
      root=new Node(data);

    }
    else
    {
      temp=root;
      while(temp.next!=null)
      {
        temp=temp.next;
      }

      Node newNode=new Node(data);
      temp.next=newNode;
    }
  }//end of insert

  public void display(Node head)
  {
    while(head!=null)
    {
      System.out.println(head.data);
      head=head.next;
    }

  }

  public Node reverseLinkedList(Node head)
  {
    Node newNode;
    Node tempr=null;
    while(head!=null)
    {
      newNode=new Node(head.data);
      newNode.next=tempr;
      tempr=newNode;
      head=head.next;
    }
    return tempr;
  }
  public static void main(String[] args) {

    ReverseLinkedList r=new ReverseLinkedList();
    r.insert(10);
    r.insert(20);
    r.insert(30);
    r.display(root);
    Node t=r.reverseLinkedList(root);
    r.display(t);
  }

}

InformationsquelleAutor der Antwort user7258708

-1

public class Linkedtest {
    public static void reverse(List<Object> list) {

        int lenght = list.size();
        for (int i = 0; i < lenght / 2; i++) {
            Object as = list.get(i);
            list.set(i, list.get(lenght - 1 - i));
            list.set(lenght - 1 - i, as);
        }
    }
    public static void main(String[] args) {
        LinkedList<Object> st = new LinkedList<Object>();
        st.add(1);
        st.add(2);
        st.add(3);
        st.add(4);
        st.add(5);
        Linkedtest.reverse(st);
        System.out.println("Reverse Value will be:"+st);
    }
}

Dies wird nützlich sein, für jede Art von collection-Objekt.

InformationsquelleAutor der Antwort user3782758

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.