Exchange first and last nodes in Circular Linked List

Given a Circular linked list exchange the first and the last node. The task should be
done with only one extra node, you can not declare more than one extra node and
also you are not allowed to declare any other temporary variable.
Note: Extra node means need of a node to traverse a list.

Examples:
Input : 5 4 3 2 1
Output : 1 4 3 2 5

Input : 6 1 2 3 4 5 6 7 8 9
Output : 9 1 2 3 4 5 6 7 8 6
We first find pointer to previous of last node. Let this node be p. Now we change next
links so that the last and first nodes are swapped.

 C++
 Java
 C#
filter_none
edit
play_arrow
brightness_4
// CPP program to exchange first and
// last node in circular linked list
#include<bits/stdc++.h>
using namespace std;

struct Node
{
 int data;
struct Node *next;
};

struct Node *addToEmpty(struct Node *head, int data)

{
// This function is only for empty list
if (head != NULL)
return head;

// Creating a node dynamically.

struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;
head = temp;

// Creating the link.

head -> next = head;

return head;
}

struct Node *addBegin(struct Node *head, int data)

{
if (head == NULL)
return addToEmpty(head, data);

struct Node *temp =

(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = head -> next;
head -> next = temp;

return head;
}

/* function for traversing the list */

void traverse(struct Node *head)
{
struct Node *p;

// If list is empty, return.

if (head == NULL)
{
cout << "List is empty." << endl;
return;
}

// Pointing to first Node of the list.

p = head;

// Traversing the list.

do
{
cout << p -> data << " ";
 p = p -> next;

} while(p != head);
}

/* Function to exchange first and last node*/

struct Node *exchangeNodes(struct Node *head)
{
// Find pointer to previous of last node
struct Node *p = head;
while (p->next->next != head)
p = p->next;

/* Exchange first and last nodes using

head and p */
p->next->next = head->next;
head->next = p->next;
p->next = head;
head = head->next;

return head;
}

// Driven Program
int main()
{
int i;
struct Node *head = NULL;
head = addToEmpty(head, 6);

for (i = 5; i > 0; i--)

head = addBegin(head, i);
cout << "List Before: ";
traverse(head);
cout << endl;

cout << "List After: ";

head = exchangeNodes(head);
traverse(head);

return 0;
}

Output:
List Before: 6 1 2 3 4 5
List After: 5 1 2 3 4 6
Split a Circular Linked List into two halves

Original Linked List

Result Linked List 1

Result Linked List 2

Thanks to Geek4u for suggesting the algorithm.
1) Store the mid and last pointers of the circular linked list using tortoise and hare
algorithm.
2) Make the second half circular.
3) Make the first half circular.
4) Set head (or start) pointers of the two linked lists.
In the below implementation, if there are odd nodes in the given circular linked list
then the first result list has 1 more node than the second result list.
 C
 Java
 Python
filter_none
edit
play_arrow
brightness_4
/* Program to split a circular linked list into two halves */
#include<stdio.h>
#include<stdlib.h>

/* structure for a node */

struct Node
{
int data;
struct Node *next;
};

/* Function to split a list (starting with head) into two lists.

head1_ref and head2_ref are references to head nodes of
the two resultant linked lists */
void splitList(struct Node *head, struct Node **head1_ref,
struct Node **head2_ref)
{
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;

if(head == NULL)
return;

/* If there are odd nodes in the circular list then

fast_ptr->next becomes head and for even nodes
fast_ptr->next->next becomes head */
while(fast_ptr->next != head &&
fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}

/* If there are even elements in list then move fast_ptr */

if(fast_ptr->next->next == head)
fast_ptr = fast_ptr->next;

/* Set the head pointer of first half */

*head1_ref = head;

/* Set the head pointer of second half */

if(head->next != head)
*head2_ref = slow_ptr->next;

/* Make second half circular */

fast_ptr->next = slow_ptr->next;
 /* Make first half circular */
slow_ptr->next = head;
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of a Circular
linked list */
void push(struct Node **head_ref, int data)
{
struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;

/* If linked list is not NULL then set the next of

last node */
if(*head_ref != NULL)
{
while(temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */

*head_ref = ptr1;
}

/* Function to print nodes in a given Circular linked list */

void printList(struct Node *head)
{
struct Node *temp = head;
if(head != NULL)
{
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != head);
}
}

/* Driver program to test above functions */

int main()
{
int list_size, i;

/* Initialize lists as empty */

struct Node *head = NULL;
struct Node *head1 = NULL;
struct Node *head2 = NULL;

/* Created linked list will be 12->56->2->11 */

push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
 printf("Original Circular Linked List");
printList(head);

/* Split the list */

splitList(head, &head1, &head2);

printf("\nFirst Circular Linked List");

printList(head1);

printf("\nSecond Circular Linked List");

printList(head2);

getchar();
return 0;
}
Output:
Original Circular Linked List
11 2 56 12
First Circular Linked List
11 2
Second Circular Linked List
56 12
Time Complexity: O(n)

Sorted insert for circular linked list

Difficulty Level: Rookie
Write a C function to insert a new value in a sorted Circular Linked List (CLL). For
example, if the input CLL is following.

Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated
node. Let the pointer to the new node be new_node. After memory allocation,
following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
 (a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;

// C++ program for sorted insert

// in circular linked list
#include <bits/stdc++.h>
using namespace std;

/* structure for a node */

class Node
{
public:
int data;
Node *next;
};

/* function to insert a new_node in a list in sorted way.

Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(Node** head_ref, Node* new_node)
{
Node* current = *head_ref;

// Case 1 of the above algo

if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}

// Case 2 of the above algo

else if (current->data >= new_node->data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
 }

// Case 3 of the above algo

else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref &&
current->next->data < new_node->data)
current = current->next;

new_node->next = current->next;
current->next = new_node;
}
}

/* Function to print nodes in a given linked list */

void printList(Node *start)
{
Node *temp;

if(start != NULL)
{
temp = start;
do {
cout<<temp->data<<" ";
temp = temp->next;
} while(temp != start);
}
}

/* Driver code */
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;

/* start with empty linked list */

Node *start = NULL;
Node *temp;

/* Create linked list from the array arr[].

Created linked list will be 1->2->11->12->56->90 */
for (i = 0; i< 6; i++)
{
temp = new Node();
temp->data = arr[i];
sortedInsert(&start, temp);
}

printList(start);

return 0;
}

// This code is contributed by rathbhupendra.

Output:
1 2 11 12 56 90
Time Complexity: O(n) where n is the number of nodes in the given linked list.

Sort the biotonic doubly linked list

Sort the given biotonic doubly linked list. A biotonic doubly linked list is a doubly
linked list which is first increasing and then decreasing. A strictly increasing or a
strictly decreasing list is also a biotonic doubly linked list.
Examples:

// C++ implementation to sort the biotonic 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 reverse a Doubly Linked List

void reverse(struct Node** head_ref)
{
struct Node* temp = NULL;
struct Node* current = *head_ref;

// 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_ref = temp->prev;
}

// Function to merge two sorted doubly linked lists

struct Node* merge(struct Node* first, struct Node* second)
{
 // If first linked list is empty
if (!first)
return second;

// If second linked list is empty

if (!second)
return first;

// Pick the smaller value

if (first->data < second->data) {
first->next = merge(first->next, second);
first->next->prev = first;
first->prev = NULL;
return first;
} else {
second->next = merge(first, second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}

// function to sort a biotonic doubly linked list

struct Node* sort(struct Node* head)
{
// if list is empty or if it contains a single
// node only
if (head == NULL || head->next == NULL)
return head;

struct Node* current = head->next;

while (current != NULL) {

// if true, then 'current' is the first node

// which is smaller than its previous node
if (current->data < current->prev->data)
break;

// move to the next node

current = current->next;
}

// if true, then list is already sorted

if (current == NULL)
return head;

// spilt into two lists, one starting with 'head'

// and other starting with 'current'
current->prev->next = NULL;
current->prev = NULL;

// reverse the list starting with 'current'

reverse(¤t);

// merge the two lists and return the

// final merged doubly linked list
return merge(head, current);
}

// 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:

// 2<->5<->7<->12<->10<->6<->4<->1
push(&head, 1);
push(&head, 4);
push(&head, 6);
push(&head, 10);
push(&head, 12);
push(&head, 7);
push(&head, 5);
push(&head, 2);
 cout << "Original Doubly linked list:n";
printList(head);

// sort the biotonic DLL

head = sort(head);

cout << "\nDoubly linked list after sorting:n";

printList(head);

return 0;
}
Output:
Original Doubly linked list:
2 5 7 12 10 6 4 1
Doubly linked list after sorting:
1 2 4 5 6 7 10 12
Time Complexity: O(n)

Convert a Binary Tree to a Circular Doubly Link List

Given a Binary Tree, convert it to a Circular Doubly Linked List (In-Place).
 The left and right pointers in nodes are to be used as previous and next pointers
respectively in converted Circular Linked List.
 The order of nodes in List must be same as Inorder of the given Binary Tree.
 The first node of Inorder traversal must be head node of the Circular List.
Example:
 Recommended: Please solve it on “PRACTICE” first, before moving on to
the solution.

The idea can be described using below steps.

1) Write a general purpose function that concatenates two given circular doubly lists
(This function is explained below).
2) Now traverse the given tree
….a) Recursively convert left subtree to a circular DLL. Let the converted list be
leftList.
….a) Recursively convert right subtree to a circular DLL. Let the converted list be
rightList.
….c) Make a circular linked list of root of the tree, make left and right of root to point
to itself.
….d) Concatenate leftList with list of single root node.
….e) Concatenate the list produced in step above (d) with rightList.
Note that the above code traverses tree in Postorder fashion. We can traverse in
inorder fashion also. We can first concatenate left subtree and root, then recur for
right subtree and concatenate the result with left-root concatenation.
How to Concatenate two circular DLLs?
 Get the last node of the left list. Retrieving the last node is an O(1) operation, since the
prev pointer of the head points to the last node of the list.
 Connect it with the first node of the right list
 Get the last node of the second list
 Connect it with the head of the list.
Below are implementations of above idea.

 C++
 Java
 Python3
 C#
filter_none
edit
play_arrow
brightness_5
// C++ Program to convert a Binary Tree

// to a Circular Doubly Linked List

#include<iostream>

using namespace std;

// To represents a node of a Binary Tree

struct Node

struct Node *left, *right;

int data;

};

// A function that appends rightList at the end

// of leftList.

Node *concatenate(Node *leftList, Node *rightList)

// If either of the list is empty

// then return the other list

if (leftList == NULL)

return rightList;

if (rightList == NULL)

return leftList;

// Store the last Node of left List

Node *leftLast = leftList->left;

// Store the last Node of right List

Node *rightLast = rightList->left;

// Connect the last node of Left List

// with the first Node of the right List

leftLast->right = rightList;

rightList->left = leftLast;

// Left of first node points to

// the last node in the list

leftList->left = rightLast;

// Right of last node refers to the first

 // node of the List

rightLast->right = leftList;

return leftList;

// Function converts a tree to a circular Linked List

// and then returns the head of the Linked List

Node *bTreeToCList(Node *root)

if (root == NULL)

return NULL;

// Recursively convert left and right subtrees

Node *left = bTreeToCList(root->left);

Node *right = bTreeToCList(root->right);

// Make a circular linked list of single node

// (or root). To do so, make the right and

// left pointers of this node point to itself

root->left = root->right = root;

// Step 1 (concatenate the left list with the list

// with single node, i.e., current node)

// Step 2 (concatenate the returned list with the

// right List)

return concatenate(concatenate(left, root), right);

// Display Circular Link List

void displayCList(Node *head)

cout << "Circular Linked List is :\n";

 Node *itr = head;

do

cout << itr->data <<" ";

itr = itr->right;

} while (head!=itr);

cout << "\n";

// Create a new Node and return its address

Node *newNode(int data)

Node *temp = new Node();

temp->data = data;

temp->left = temp->right = NULL;

return temp;

// Driver Program to test above function

int main()

Node *root = newNode(10);

root->left = newNode(12);

root->right = newNode(15);

root->left->left = newNode(25);

root->left->right = newNode(30);

root->right->left = newNode(36);

Node *head = bTreeToCList(root);

displayCList(head);

return 0;
}

Output:
Circular Linked List is :
25 12 30 10 36 15

Josephus Circle using circular linked list

There are n people standing in a circle waiting to be executed. The counting out
begins at some point in the circle and proceeds around the circle in a fixed direction.
In each step, a certain number of people are skipped and the next person is
executed. The elimination proceeds around the circle (which is becoming smaller
and smaller as the executed people are removed), until only the last person remains,
who is given freedom. Given the total number of persons n and a number m which
indicates that m-1 persons are skipped and m-th person is killed in circle. The task is
to choose the place in the initial circle so that you are the last one remaining and so
survive.
Examples :
Input : Length of circle : n = 4
Count to choose next : m = 2
Output : 1

Input : n = 5
m = 3
Output : 4
We have discussed different solutions of this problem (here and here). In this post a
simple circular linked list based solution is discussed.
1) Create a circular linked list of size n.
2) Traverse through linked list and one by one delete every m-th node until there is one node
left.
3) Return value of the only left node.
// CPP program to find last man standing
#include<bits/stdc++.h>
using namespace std;

/* structure for a node in circular

linked list */
struct Node
{
int data;
struct Node *next;
};

// To create a new node of circular

// linked list
Node *newNode(int data)
{
Node *temp = new Node;
temp->next = temp;
temp->data = data;
}

/* Function to find the only person left

after one in every m-th node is killed
in a circle of n nodes */
void getJosephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node *head = newNode(1);
Node *prev = head;
for (int i = 2; i <= n; i++)
{
prev->next = newNode(i);
prev = prev->next;
}
prev->next = head; // Connect last
// node to first

/* while only one node is left in the

linked list*/
Node *ptr1 = head, *ptr2 = head;
while (ptr1->next != ptr1)
{
// Find m-th node
int count = 1;
while (count != m)
{
ptr2 = ptr1;
ptr1 = ptr1->next;
count++;
}

/* Remove the m-th node */

ptr2->next = ptr1->next;
ptr1 = ptr2->next;
}

printf ("Last person left standing "

"(Josephus Position) is %d\n ",
ptr1->data);
}

/* Driver program to test above functions */

int main()
{
int n = 14, m = 2;
getJosephusPosition(m, n);
return 0;
}
Output :
Last person left standing (Josephus Position) is 13
Time complexity: O(m * n)