Exchange the first and last nodes in Circular Linked List

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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).