Обратный одиночный список Java

Ответ 1

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:      >  >  >

Ответ 2

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

Ответ 3

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

Collections.reverse(list);

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

Ответ 4

Метод реверсирования связанного списка выглядит следующим образом:

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

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, входящие

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

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

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 

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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;

}

Ответ 10

Используйте это.

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 для изменения единого списка

Ответ 11

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

if(next == null)
     return;

В начале вашего цикла.

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

while(tmp != null){

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

Ответ 12

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

Ответ 13

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

    }

}

Ответ 14

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

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

Ответ 15

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

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

Мне это легче.

Ответ 16

открытый класс 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;
    }

}

}

Ответ 17

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

Ответ 18

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

Ответ 19

Чтобы отменить одноуровневый список, вы должны иметь три узла: верх, beforeTop и AfterTop. Top является заголовком односвязного списка, поэтому beforeTop будет иметь значение null и afterTop будет следующим элементом top и с каждой итерацией двигаться вперед 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;
    }

Ответ 20

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

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

Ответ 21

    // 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 

Ответ 22

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

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

Ответ 23

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

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