How to convert circular linked list into singly linked list

Question

First, I make circular linked list that look like

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (head)

Now, I am trying to convert this circular linked list into singly linked list that's my expected output. I'm trying to remove circularity by adding null in place of (head).

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Here down is details of methods which is declared in my code:

add(arg) : Adding Node from last in circular linked list.
detectCycle() : Detect, linked list is circular or singly.
detectFirstNode() : If linked list is cyclic, Detect first node where cycle is created.
printList() : Print the circular linked list.
printList2() : Print the singly linked list after convert circular to singly linked list.

Here down is my code:

public class Main
{
    class Node
    {
        Integer data;
        Node next;
        Node(Integer data)
        {
            this.data = data;
            this.next = null;
        }
    }
    
    Node head = null;
    Node tail = null;
    
    public void add(Integer data)
    {
        Node newNode = new Node(data);
        if(head == null)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail.next = newNode;
        }
        
        tail = newNode;
        tail.next = head;
    }
    
    public Node detectCycle()
    {
        if(head == null)
        {
            System.out.print("list is empty");
        }
        
        Node slow = head;
        Node fast = head;
        while(fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow)
            {
                return slow;
            }
        }
        return null;
    }
    
    public Integer detectFirstNode()
    {
        Node meetingNode = detectCycle();
        Node start = head;
        // Here i want to remove connection of that node with null who create circular linked list
        
        while(start != meetingNode)
        {
            meetingNode = meetingNode.next;
            start = start.next;
        }
        
        return start.data;
    }
    
    public void printList()
    {
        Node curr = head;
        do
        {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }while(curr != head);
    }
    
    public void printList2()
    {
        Node currNode = head;
        while(currNode != null)
        {
            System.out.print(currNode.data + " -> ");
            currNode = currNode.next;
        }
        System.out.println("null");
    }
    
    public static void main(String[] args) {
        Main m = new Main();
        m.add(1);
        m.add(2);
        m.add(3);
        m.add(4);
        m.add(5);
        m.add(6);
        
        m.printList();
        System.out.println("\nFirst Node who create circular linked list is : " + m.detectFirstNode());
        m.printList2();
    }
}

Faheem azaz Bhanej · Accepted Answer · 2022-05-05 14:20:48Z

2

In your Detect first node method change it to do-while and when you encounter the first node as the meeting nodes next, exit and make it null.

public Integer detectFirstNode() {

    Node meetingNode = detectCycle();
    Node start = head;

    do{
        meetingNode = meetingNode.next;
    } while (start != meetingNode.next);

    meetingNode.next = null;

    return start.data;
}

edited May 5, 2022 at 14:20

Faheem azaz Bhanej

2,4063 gold badges17 silver badges38 bronze badges

answered May 5, 2022 at 13:56

Shubham Saraswat

5594 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ashish Patil · Accepted Answer · 2022-05-05 14:01:05Z

2

If I understand your question properly, I will suggest to modify printList2() method something like below:

public void printList2() {
            Node currNode = head;
    
            while (currNode != null) {
                System.out.print(currNode.data + " -> ");
                if (currNode.next.data == this.detectFirstNode())
                    currNode = null;
                else
                    currNode = currNode.next;
            }
            System.out.println("null");
        }

answered May 5, 2022 at 14:01

Ashish Patil

4,6421 gold badge17 silver badges38 bronze badges

Comments

siroWall · Accepted Answer · 2022-05-09 10:30:54Z

0

I saw that you were using 2 pointers:

head: points to first node of the circular linked list
tail: points to last node of the circular linked list, tail -> next points to head

Your question is how to convert circular linked list to singly linked list. Obviously, you only point tail -> next to null instead of head

answered May 9, 2022 at 10:30

siroWall

1

Collectives™ on Stack Overflow

How to convert circular linked list into singly linked list

Here down is details of methods which is declared in my code:

Here down is my code:

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Here down is details of methods which is declared in my code:

Here down is my code:

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related