Doubly Linked List – Test
Qus 1 : Reverse a doubly linked list
Level- Medium
You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty. Change the next and prev pointers of all the nodes so that the direction of the list is
reversed. Return a reference to the head node of the reversed list.
Function Description
Complete the reverse function in the editor below. It should return a reference to the head of your reversed list.
reverse has the following parameter(s):
head: a reference to the head of a DoublyLinkedList
Input Format
The first line contains an integer , the number of test cases.
Each test case is of the following format:
The first line contains an integer , the number of elements in the linked list.
The next lines contain an integer each denoting an element of the linked list.
Constraints
Output Format
Return a reference to the head of your reversed list. The provided code will print the reverse array as a one line of space-separated integers for each test case.
Sample Input
1
4
1
2
3
4
Sample Output
4321
Explanation
The initial doubly linked list is:
The reversed doubly linked list is:
All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.
// Java program to reverse a doubly linked list
class LinkedList {
static Node head;
static class Node {
int data;
Node next, prev;
Node(int 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 beginging of the Doubly Linked List */
void push(int new_data) {
/* allocate node */
Node new_node = new Node(new_data);
/* since we are adding at the begining,
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 lsit */
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(2);
list.push(4);
list.push(8);
list.push(10);
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);
// This code has been contributed by Mayank Jaiswal
Qus 2 : Sort a k sorted doubly linked list
Level – Hard
Given a doubly linked list containing n nodes, where each node is at most k away from its target position in the list. The problem is to sort the given doubly linked list.
For example, let us consider k is 2, a node at position 7 in the sorted doubly linked list, can be at positions 5, 6, 7, 8, 9 in the given doubly linked list.
Examples:
Naive Approach: Sort the given doubly linked list using insertion sort technique.
Time Complexity: O(nk)
Auxiliary Space: O(1)
Efficient Approach: We can sort the list using the MIN HEAP data structure. The approach has been explained in Sort a nearly sorted (or K sorted) array. We only have to be careful while traversing the input doubly linked list and
adjusting the required next and previous links in the final sorted list.
#include <bits/stdc++.h>
using namespace std;
// a node of the doubly
linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// 'compare' function used
to build up the
// priority queue
struct compare {
bool operator()(struct
Node* p1, struct Node* p2)
{
return p1->data >
p2->data;
}
};
// function to sort a k
sorted doubly linked list
struct Node*
sortAKSortedDLL(struct
Node* head, int k)
{
// if list is empty
if (head == NULL)
return head;
// priority_queue 'pq'
implemeted as min heap
with the
// help of 'compare'
function
priority_queue<Node*,
vector<Node*>, compare>
pq;
struct Node* newHead =
NULL, *last;
// Create a Min Heap
of first (k+1) elements
from
// input doubly linked
list
for (int i = 0; head !=
NULL && i <= k; i++) {
// push the node
on to 'pq'
pq.push(head);
// move to the
next node
head = head->next;
}
// loop till there are
elements in 'pq'
while (!pq.empty()) {
// place root or
top of 'pq' at the end of
the
// result sorted
list so far having the
first node
// pointed to by
'newHead'
// and adjust the
required links
if (newHead ==
NULL) {
newHead =
pq.top();
newHead->prev
= NULL;
// 'last'
points to the last node
// of the
result sorted list so far
last =
newHead;
}
else {
last->next =
pq.top();
pq.top()->prev
= last;
last =
pq.top();
}
// remove element
from 'pq'
pq.pop();
// if there are
more nodes left in the
input list
if (head != NULL)
{
// push the
node on to 'pq'
pq.push(head);
// move to the
next node
head = head-
>next;
}
}
// making 'next' of
last node point to NULL
last->next = NULL;
// new head of the
required sorted DLL
return newHead;
}
// Function to insert a
node at the beginning
// of the Doubly Linked
List
void push(struct Node**
head_ref, int new_data)
{
// allocate node
struct Node* new_node
=
(struct
Node*)malloc(sizeof(struct
Node));
// put in the data
new_node->data =
new_data;
// since we are adding
at the begining,
// prev is always NULL
new_node->prev = NULL;
// link the old list
off the new node
new_node->next =
(*head_ref);
// change prev of head
node to new node
if ((*head_ref) !=
NULL)
(*head_ref)->prev
= new_node;
// move the head to
point to the new node
(*head_ref) =
new_node;
}
// Function to print nodes
in a given doubly linked
list
void printList(struct Node*
head)
{
// if list is empty
if (head == NULL)
cout << "Doubly
Linked list empty";
while (head != NULL) {
cout << head->data
<< " ";
head = head->next;
}
}
// Driver program to test
above
int main()
{
struct Node* head =
NULL;
// Create the doubly
linked list:
// 3<->6<->2<->12<-
>56<->8
push(&head, 8);
push(&head, 56);
push(&head, 12);
push(&head, 2);
push(&head, 6);
push(&head, 3);
int k = 2;
cout << "Original
Doubly linked list:n";
printList(head);
// sort the biotonic
DLL
head =
sortAKSortedDLL(head, k);
cout << "\nDoubly
linked list after
sorting:n";
printList(head);
return 0;
}
Output:
Original Doubly linked list:
3 6 2 12 56 8
Doubly linked list after sorting:
2 3 6 8 12 56
Time Complexity: O(nLogk)
Auxiliary Space: O(k)
Qus 3 : Remove duplicates from a sorted doubly linked list
Level – Hard
Given a sorted doubly linked list containing n nodes. The problem is to remove duplicate nodes from the given list.
Examples:
Algorithm:
removeDuplicates(head_ref, x)
if head_ref == NULL
return
Initialize current = head_ref
while current->next != NULL
if current->data == current->next->data
deleteNode(head_ref, current->next)
else
current = current->next
The algorithm for deleteNode(head_ref, current) (which deletes the node using the pointer to the node) is discussed in this post.
/* C++ implementation to remove
duplicates from a
sorted doubly linked list */
#include <bits/stdc++.h>
using namespace std;
/* a node of the doubly linked
list */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Function to delete a node in
a Doubly Linked List.
head_ref --> pointer to head
node pointer.
del --> pointer to node to
be deleted. */
void deleteNode(struct Node**
head_ref, struct Node* del)
{
/* base case */
if (*head_ref == NULL || del
== NULL)
return;
/* If node to be deleted is
head node */
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node
to be deleted
is NOT the last node */
if (del->next != NULL)
del->next->prev = del-
>prev;
/* Change prev only if node
to be deleted
is NOT the first node */
if (del->prev != NULL)
del->prev->next = del-
>next;
/* Finally, free the memory
occupied by del*/
free(del);
}
/* function to remove duplicates
from a
sorted doubly linked list */
void removeDuplicates(struct
Node** head_ref)
{
/* if list is empty */
if ((*head_ref) == NULL)
return;
struct Node* current =
*head_ref;
struct Node* next;
/* traverse the list till
the last node */
while (current->next !=
NULL) {
/* Compare current node
with next node */
if (current->data ==
current->next->data)
/* delete the node
pointed to by
'current->next' */
deleteNode(head_ref,
current->next);
/* else simply move to
the next node */
else
current = current-
>next;
}
}
/* Function to insert a node at
the beginning
of the Doubly Linked List */
void push(struct Node** head_ref,
int new_data)
{
/* allocate node */
struct Node* new_node =
(struct
Node*)malloc(sizeof(struct
Node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at
the begining,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the
new node */
new_node->next =
(*head_ref);
/* change prev of head node
to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev =
new_node;
/* move the head to point to
the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a
given doubly linked list */
void printList(struct Node* head)
{
/* if list is empty */
if (head == NULL)
cout << "Doubly Linked
list empty";
while (head != NULL) {
cout << head->data << "
";
head = head->next;
}
}
/* Driver program to test above
functions*/
int main()
{
/* Start with the empty list
*/
struct Node* head = NULL;
/* Create the doubly linked
list:
4<->4<->4<->4<->6<->8<->8<-
>10<->12<->12 */
push(&head, 12);
push(&head, 12);
push(&head, 10);
push(&head, 8);
push(&head, 8);
push(&head, 6);
push(&head, 4);
push(&head, 4);
push(&head, 4);
push(&head, 4);
cout << "Original Doubly
linked list:n";
printList(head);
/* remove duplicate nodes */
removeDuplicates(&head);
cout << "\nDoubly linked
list after"
" removing
duplicates:n";
printList(head);
return 0;
}
Output:
Original Doubly linked list:
4 4 4 4 6 8 8 10 12 12
Doubly linked list after removing duplicates:
4 6 8 10 12
Time Complexity: O(n)
