Question

Method: DoublyLinkedList reverse(DoublyLinkedList list) Reverse() method accepts a DoublyLinkedList of Character as the argument, reverses the elements in the list, and returns the resulting list. For example:

The given list is

'a' 'b' 'c' 'd' 'e'

The return list should be

'e' 'd' 'c' 'b' 'a'

How can we do this in Java?

Answer 1

class LinkedList {

static Node head;

static class Node {

char data;
Node next, prev;

Node(char d) {
data = d;
next = prev = null;
}
}

/* Function to reverse a Doubly Linked List */
void reverse() {
Node temp = null;
Node current = head;

/* swap next and prev for all nodes of
doubly linked list */
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}

/* Before changing head, check for the cases like empty
list and list with only one node */
if (temp != null) {
head = temp.prev;
}
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(char new_data) {
/* allocate node */
Node new_node = new Node(new_data);

/* since we are adding at the beginning,
prev is always NULL */
new_node.prev = null;

/* link the old list off the new node */
new_node.next = head;

/* change prev of head node to new node */
if (head != null) {
head.prev = new_node;
}

/* move the head to point to the new node */
head = new_node;
}

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly 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();

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
list.push('e');
list.push('d');
list.push('c');
list.push('b');
list.push('a');

System.out.println("Original linked list ");
list.printList(head);

list.reverse();
System.out.println("");
System.out.println("The reversed Linked List is ");
list.printList(head);
}
}

Output Screenshot: