如何将循环链表转化为单向链表

Question

首先，我制作的循环链表看起来像

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

现在，我正在尝试将此循环链表转换为我预期输出的单链表。我试图通过添加 null 代替 (head).

来消除循环

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

下面是我的代码中声明的方法的详细信息：

add(arg) : 在循环链表中从最后添加Node。
detectCycle() :检测，链表是循环的还是单链的。
detectFirstNode() :如果链表是循环的，检测创建循环的第一个节点。
printList() :打印循环链表
printList2() :循环转单链表后打印单链表

下面是我的代码：

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

Answer 1

在检测第一个节点方法中将其更改为do-while，当您遇到第一个节点作为下一个会议节点时，退出并使其为空。

public Integer detectFirstNode() {

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

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

    meetingNode.next = null;

    return start.data;
}

Answer 2

如果我正确理解你的问题，我会建议修改 printList2() 方法，如下所示：

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

Answer 3

我看到你用了 2 个指针：

head：指向循环链表的第一个节点
tail：指向循环链表的最后一个节点，tail -> next指向head

你的问题是如何将循环链表转换为单链表。显然，您只将 tail -> next 指向 null 而不是 head

如何将循环链表转化为单向链表

How to convert circular linked list into singly linked list

java

linked-list

data-structures

下面是我的代码中声明的方法的详细信息：

下面是我的代码：