Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is a Circular Linked List?
1.2.
Problem statement
1.3.
Sample Examples
2.
Approach
2.1.
Why donâ€™t we go for the Naive Approach?
2.2.
What will be the optimal approach then?
2.3.
Pseudocode
2.4.
Implementation in Java
2.4.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What are the advantages of Linked List?
3.2.
What are the various types of Linked List?
3.3.
What are the basic operations that can be performed on the Linked List?
3.4.
How is the node of Linked List represented?
4.
Conclusion
Last Updated: Mar 27, 2024

# Exchange the first and last nodes in Circular Linked List

Rupal Saluja
0 upvote

## Introduction

In this blog, we will try to grab hold of a Circular Linked List data structure problem. Through that problem, we will try to understand how to approach any linked list Data Structure problem. The examples presented will help you clear your concepts, Pseudocode will provide you with an immediate solution, and the implementation part will give you a detailed understanding of every step.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

### What is a Circular Linked List?

The Circular Linked List was made to resolve the drawbacks that arose in non-circular linked lists. Circular Linked List is a linked list in which all the nodes are connected in the circular format, forming a circle. There exist no NULL value at the end. There are two types of Circular Linked List and they are:

• Singly Circular Linked List
• Doubly Circular Linked List

A Singly Circular Linked List looks like:

A Doubly Circular Linked List looks like this:

### Problem statement

We are given a Circular Linked List and we are expected to exchange the first and the last node of it. We will perform this exchange on Singly Circular Linked List, and not use Doubly Circular Linked List.

There are no assumptions and exceptions in this problem.

Also read - Merge sort in linked list

### Sample Examples

Example 1

Explanation

In the example above, we have taken a Singly Circular Linked List of five integer elements. The number of elements in the list depends on the requirement of the situation completely. To understand this a little better, please refer to the image below.

Example 2

Explanation

In the example above, we have a Doubly Circular Linked List with â€˜charâ€™ datatype. There is not much difference in concept when you are exchanging the first and the last nodes in either Singly Linked List or Doubly Linked List. To get a better understanding, please have a look at the image below.

## Approach

### Why donâ€™t we go for the Naive Approach?

What happens in the Naive Approach is that we donâ€™t exchange the nodes, we just swap their values. Only the data inside the node gets exchanged and not the memory location. The naive approach serves as a quick fix to this problem, which is not generally not recommended. In such a situation, it is better if we go with the approach given below.

### What will be the optimal approach then?

Step-1:

Firstly, we will create a singly circular linked list. To understand the approach, we have only five elements.

Step-2:

After a linked list has been created, we will create a temporary node â€˜tempâ€™ and will follow a typical swapping method to exchange the values of the first and the last node.

For that, we will store the value of the last node in the temporary node, temp. After that, the value of the first node will be put in the last node. Then, the value of the last node which was stored in the temporary node, the temp will be stored in the first node.

Refer to the following image for a better understanding.

To create a clear picture of what exactly are we doing during swapping, we have taken addresses for the first and the last node for reference.

Step-4:

Now that values have been transferred, print the complete Circular Linked List.

### Pseudocode

``````public static ListNode exchange(ListNode head) {
ListNode t=head;
while(t.next!=head){
t=t.next;
}
int temp=head.data;
head.data=t.data;
t.data=temp;
return head;
}    ``````

### Implementation in Java

``````public class Main
{
public  static class ListNode
{
int data;
ListNode next;
ListNode() {}
ListNode(int data) { this.data = data; }
ListNode(int data, ListNode next) { this.data = data; this.next = next; }
}
public static ListNode append(ListNode head,int x)
{
ListNode p;
ListNode temp=new ListNode();
temp.data=x;
if(head==null){
head=temp;
temp.next=temp;
return head;
}
p=head;
while(p.next!=head){
p=p.next;
}
p.next=temp;
temp.next=head;
return head;
}
public static void display(ListNode head)
{
ListNode p;
if(head==null)
{
System.out.println("List is empty");
return;
}
p=head;
do{
System.out.println(p.data+" ");
p=p.next;
}while(p!=head);
}
public static ListNode exchange(ListNode head)
{
ListNode t=head;
while(t.next!=head)
{
t=t.next;
}
int temp=head.data;
head.data=t.data;
t.data=temp;
return head;
}
public static void main(String[] args)
{
ListNode head=null;
head = append(head,13);
head = append(head,17);
head = append(head,23);
head = append(head,31);
head = append(head,19);
System.out.println("List Before exchanging the values");
display(head);
System.out.println("List after exchanging the values");
head=exchange(head);
display(head);
}
}``````

Input

``````List Before exchanging the values
13 17 23 31 19``````

Output

``````List after exchanging the values
19 17 23 31 13``````

#### Complexity Analysis

Time Complexity

Since we have a linked list of â€˜nâ€™ elements and we are using only one for loop to traverse the linked list there are no nested loops, therefore, the time complexity for the code mentioned above will be O(n).

Space Complexity

We have not used any extra space in the solution provided therefore the space complexity for the code mentioned above will be O(1).

## Frequently Asked Questions

### What are the advantages of Linked List?

Some of the advantages are:

• You can allocate and deallocate memory to the linked list at runtime. There is no need to specify the size initially. This is because Linked List is a dynamic data structure.
• In Linked List, memory is allocated and deallocated at the runtime. So, there is no memory wastage like in the case of the array.
• It is much easier to insert into and delete items from any of the types of Linked List.

### What are the various types of Linked List?

The various types of Linked List are:

### What are the basic operations that can be performed on the Linked List?

All the basic options that can be performed on the Linked List are mentioned in the list below.

• Insertion
• Deletion
• Display
• Search
• Delete

### How is the node of Linked List represented?

Each node of the Linked List consists of a data item and the address of another node. Both, the data item and the reference of the next node are wrapped together to form a node.

## Conclusion

In this blog we have extensively discussed the problem of exchanging the first and last nodes of a circular linked list, we looked at the problem statement, discussed sample examples to give a clear idea about what the problem is asking us to do,  after that we went through the pseudocode, and saw the implementation of in C++. In the end, we also discussed the complexity of the optimal approach.

We hope the above discussion helped you understand and solve the problem better and now it is your turn to code the problem in your own way.

If you want to practice such problems you can refer to the links given below.

For peeps out there who want to grasp more about DSA, Power programming, JavaScript, or any other technical or core topics, you can refer to guided paths on Coding Ninjas Studio. Do enroll in the courses provided by us, take mock tests and solve problems available and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.

Do upvote our blog to help fellow ninjas grow.

Happy Coding!