'How to reverse a doubly linked list?
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
Solution 1:[1]
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;
}
}
}
Solution 2:[2]
I get an idea, find doubly LinkedList's head and tail, then reverse just like normal singly linked list.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | StepUp |
| Solution 2 | LeeGoeth |
