Home > Net >  How to reverse a doubly linked list?
How to reverse a doubly linked list?

Time:04-18

I'm trying to reverse a linked list and I wrote the code for that. But, when I print the list after reversing it, the output is kinda incomplete.

public void reverseDoubly() {
    Node temp = null;
    Node current = head;
    if(current == null) System.out.println("Cannot reverse an empty list!");
    while(current!=null) {
        temp = current.previous;
        current.previous = current.next;
        current.next = temp;
        current = current.previous;
    }
    if(temp!=null) { 
        head = temp.previous;
    }
}





public class Main {

public static void main(String[] args) {
    Doubly d1 = new Doubly();
    d1.insertFirst(80);
    d1.insertLast(90);
    d1.insertLast(100);
    d1.insertLast(120);
    d1.insertAtPos(3, 110);
    d1.reverseDoubly();
    d1.print();
}}

Output: 120 110 100

CodePudding user response:

In my view temp should be head and current should be head.next.

So the code would look like this:

public void Reverse() 
{
    Node<T> previous = Head;
    Node<T> current = Head.Next;

    while (current != null)
    {
        Node<T> next = current.Next;
        current.Next = previous;
        previous = current;
        current = next;
    }

    Tail = Head;
    Tail.Next = null;
    Head = previous;
}

The complete code via C# (do not worry it is can be easily converted to C#) would look like this:

public class Node<T>
{
    public Node<T> Next { get; set; }

    public T Value { get; set; }

    public Node(T value)
    {
        Value = value;
    }

    public override string ToString()
    {
        return $"Value is {Value}";
    }
}

and LinkedList<T>:

public class LinkedList { public Node Head { get; set; }

    public Node<T> Tail { get; set; }


    public void Reverse() 
    {
        Node<T> previous = Head;
        Node<T> current = Head.Next;

        while (current != null)
        {
            Node<T> next = current.Next;
            current.Next = previous;
            previous = current;
            current = next;
        }

        Tail = Head;
        Tail.Next = null;
        Head = previous;
    }

    public void Insert(T value) 
    {
        Node<T> newNode = new Node<T>(value);
        if (Head == null)
        {
            Head = newNode;
            Tail = Head;
        }
        else 
        {
            Node<T> current = Head;
            while (current != null)
            {
                if (current.Next == null)
                {
                    current.Next = newNode;
                    current = current.Next;
                    break;
                }   
                else
                    current = current.Next;
            }
            
            Tail = current;
        }            
    }
}

CodePudding user response:

I get an idea, find doubly LinkedList's head and tail, then reverse just like normal singly linked list.

  • Related