This post is completed by 1 user
|
Add to List |
106. Reverse a Doubly-Linked List (In-place Algorithm)
Objective: Given a doubly-linked list, write an in-place algorithm to reverse the list.
Example:
![Reverse The Doubly Linked List](/static/media/algorithms/2015/01/Reverse-The-Doubly-Linked-List.png)
Approach:
- Every Node in a doubly-linked list has the next and previous pointer.
- Do the linear traversal of the linked list and keep swapping the next and previous pointers.
- In the end, make the last pointer the head of the list.
public class Main {
public static Node head=null;
public static Node tail = null;
public static int size = 0;
public Node reverseDLL(){
Node current = head;
Node temp = null;
while(current!=null){
temp = current.prev; //swap the next and prev pointer
current.prev = current.next;
current.next = temp;
current = current.prev;
}
return temp.prev;
}
public void print(Node head){
Node current = head;
while(current!=null){
System.out.print(" " + current.data);
current = current.next;
}
}
public void add(int data){
Node n = new Node(data);
if(head==null){
head = n;
tail = n;
}else{
head.prev = n;
n.next = head;
head = n;
}
size++;
}
public static void main(String args[]){
Main r = new Main();
r.add(1);r.add(2);r.add(3);r.add(4);
r.print(head);
Node x = r.reverseDLL();
System.out.println("");
r.print(x);
}
}
class Node{
int data;
Node next;
Node prev;
public Node(int data){
this.data =data;
this.next = null;
this.prev = null;
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class Main:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def reverse_dll(self):
current = self.head
temp = None
while current:
temp = current.prev # swap the next and prev pointer
current.prev = current.next
current.next = temp
current = current.prev
return temp.prev
def print_list(self, head):
current = head
while current:
print(" ", current.data, end="")
current = current.next
print()
def add(self, data):
n = Node(data)
if not self.head:
self.head = n
self.tail = n
else:
self.head.prev = n
n.next = self.head
self.head = n
self.size += 1
if __name__ == "__main__":
r = Main()
r.add(1)
r.add(2)
r.add(3)
r.add(4)
r.print_list(r.head)
x = r.reverse_dll()
r.print_list(x)
package main
import "fmt"
type Node struct {
data int
next *Node
prev *Node
}
type Main struct {
head *Node
tail *Node
size int
}
func (m *Main) reverseDLL() *Node {
current := m.head
var temp *Node
for current != nil {
temp = current.prev // swap the next and prev pointer
current.prev = current.next
current.next = temp
current = current.prev
}
return temp.prev
}
func (m *Main) printList(head *Node) {
current := head
for current != nil {
fmt.Printf(" %d", current.data)
current = current.next
}
fmt.Println()
}
func (m *Main) add(data int) {
n := &Node{data: data}
if m.head == nil {
m.head = n
m.tail = n
} else {
m.head.prev = n
n.next = m.head
m.head = n
}
m.size++
}
func main() {
r := &Main{}
r.add(1)
r.add(2)
r.add(3)
r.add(4)
r.printList(r.head)
x := r.reverseDLL()
r.printList(x)
}
Output:
->4->3->2->1 ->1->2->3->4