This post is completed by 1 user

  • 0
Add to List
Medium

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

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