Обратный односвязный список Java

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

Так что же происходит, когда tmp == null?

Впрочем, ты почти угадал.

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

Или в более красивом (?) Названии:

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

ASCII-арт:

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

Ниже приведен метод реверсирования связанного списка.

Обратный метод

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
}

Для реверсирования списка необходимы три ссылки: pre, curr, incoming.

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

Чтобы изменить узел, вам нужно сохранить предыдущийэлемент, чтобы вы могли использовать простой оператор;

curr.next = pre;

Чтобы изменить направление текущего элемента. Однако для итерации по списку вы должны сохранить входящий элемент до выполнения приведенного выше оператора, потому что при реверсировании следующей ссылки текущего элемента вы больше не знаете входящий элемент, поэтому нужна третья ссылка.

Демонстрационный код показан ниже;

Образец класса LinkedList

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();
        }

    }

}

Тестовый код

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();
    }

}

Выход

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

Если это не домашнее задание, и вы делаете это «вручную» специально, то я бы рекомендовал использовать

Collections.reverse(list);

Collections.reverse() возвращает void, и ваш список переворачивается после вызова.

У нас может быть три узла: предыдущий, текущий и следующий.

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;
}

Я знаю, что рекурсивное решение не является оптимальным, но просто хотел добавить его сюда:

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);
        }
    }
}

Я не понимаю... почему бы не сделать это:

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;
}

Я нахожу это проще.

Более элегантным решением было бы использовать рекурсию

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

Я попробовал приведенный ниже код, и он отлично работает:

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;
}

В основном один за другим он устанавливает следующий указатель одного узла на его следующий за следующим узлом, поэтому, начиная со следующего, все узлы присоединяются в конце списка.

Я думаю, ваша проблема в том, что атрибут вашего изначально последнего элемента next не изменяется из-за вашего состояния

if(next == null)
     return;

Находится в начале вашего цикла.

Я бы переместил его сразу после назначения tmp.next:

while(tmp != null){

  tmp.next = before;
  if(next == null)
     return;
  before = tmp;
  tmp = next;
  next = next.next;
}

Использовать это.

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

или Java-программа для реверсирования односвязного списка

Вы также можете попробовать это

    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());

Чтобы перевернуть односвязный список, у вас должно быть три узла: top, beforeTop и AfterTop. Top является заголовком односвязного списка, поэтому beforeTop будет нулевым, а afterTop будет следующим элементом top, и с каждой итерацией будет двигаться вперед < strong>beforeTop назначается top, а top назначается afterTop (т. е. top). далее).

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;
    }

Использование рекурсии Это слишком просто:

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;
}

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;
}

Используйте приведенную выше функцию, чтобы отменить односвязный список.

 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;
}

проверьте дополнительные сведения об анализе сложности http://javamicro.com/ref-card/DS-Algo/How-to-Reverse-Singly-Linked-List?

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);
    }
}

Это будет полезно для любого типа объекта коллекции.