How to convert circular linked list into singly linked list?

Discussion in 'C' started by Tabb1us, Jun 22, 2022.

  1. Tabb1us

    Tabb1us New Member

    Joined:
    Jun 20, 2022
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    1
    Gender:
    Male
    First, I create a circular linked list that looks like this:
    Code:
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (head)
    Now I'm attempting to convert this circular linked list into a singly linked list, which is the desired result. I'm attempting to eliminate circularity by substituting null for (head).
    Code:
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
    This is my code:
    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();
        }
    }
    Can someone assist me?
     
  2. Tabb1us

    Tabb1us New Member

    Joined:
    Jun 20, 2022
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    1
    Gender:
    Male
    Code:
    public Integer detectFirstNode() {
    
    
        Node meetingNode = detectCycle();
        Node start = head;
    
        do{
            meetingNode = meetingNode.next;
        } while (start != meetingNode.next);
    
        meetingNode.next = null;
    
        return start.data;
    }
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,367
    Likes Received:
    386
    Trophy Points:
    83
    What issue are you facing? I mean what assistance do you need?
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice