algorithm - 将循环链表分成两半

Question

我正在处理将循环链表分成两半的问题。如果列表是偶数，则拆分将导致两个偶数列表。如果拆分是奇数，则第一个列表将具有额外的节点。

以下是我的节点类的代码

public class CLLNode {

    private int data;
    private CLLNode next;

    public CLLNode(int d)
    {
        this.data = d;
    }

    public void setData(int d)
    {
        this.data = d;
    }

    public int getData()
    {
        return this.data;
    }

    public void setNext(CLLNode n)
    {
        this.next = n;
    }

    public CLLNode getNext()
    {
        return this.next;
    }

}

以下是我的循环链表类的代码

public class CLinkedList {

    private CLLNode Head;

    public CLinkedList()
    {
        Head = null;
    }

    public CLLNode getHead()
    {
        return this.Head;   
    }

    public void insertFirst(int d)
    {
        CLLNode n = new CLLNode(d);
        if(Head == null)
        {
            this.Head = n;
            n.setNext(n);
        }
        else
        {
            CLLNode temp = this.Head;
            while(temp.getNext()!= this.Head)
            {
                temp = temp.getNext();
            }
            n.setNext(this.Head);
            temp.setNext(n);
            this.Head = n;
        }
    }

    public void insertLast(int d)
    {
        CLLNode n = new CLLNode(d);
        if(Head == null)
        {
            this.Head = n;
            n.setNext(n);
        }
        else
        {
            CLLNode temp = this.Head;
            while(temp!= null)
            {
                temp = temp.getNext();
                if(temp.getNext() == this.Head)
                {
                    break;
                }
            }

            n.setNext(temp.getNext());
            temp.setNext(n);
        }

    }

    public void deleteFirst()
    {
        CLLNode temp = this.Head;
        CLLNode temp2 = this.Head;

        while(temp2!=null)
        {
            temp2 = temp2.getNext();
            if(temp2.getNext()== this.Head)
            {
                break;
            }
        }

        temp2.setNext(temp.getNext());
        this.Head = temp.getNext();
        temp.setNext(null);
    }

    public void deleteLast()
    {
        CLLNode temp = this.Head;
        CLLNode temp2 = this.Head;

        while(temp.getNext()!= this.Head)
        {
            temp2 = temp;
            temp = temp.getNext();
        }

        temp2.setNext(temp.getNext());
        temp = null;
    }

    public void displayList(CLLNode n)
    {
        CLLNode temp = n;
        while(temp!= null)
        {
            System.out.println(temp.getData());
            temp = temp.getNext();
            if(temp == this.Head)
            {
                break;
            }
        }
    }

    public int getLength()
    {
        int count  = 0;
        CLLNode temp = this.Head;
        while(temp != null)
        {
            count ++;
            temp = temp.getNext();
            if(temp == this.Head){
                break;
                }
        }

        return count;
    }

    public void splitList(CLLNode head, CLLNode head1, CLLNode head2)
    {
        CLLNode temp1 = head;
        CLLNode temp2 = head;
        CLLNode temp3 = head;

        while(temp2!=null)
        {
            temp1 = temp1.getNext();
            temp2 = temp2.getNext().getNext();

            if(temp2.getNext()== head)
            {
                temp2.setNext(temp1.getNext());
                head2 = temp1.getNext();
                temp1.setNext(temp3);
                head1 = temp3;
                break;
            }

            if(temp2.getNext().getNext()==head)
            {
                temp2.getNext().setNext(temp1.getNext());
                head2 = temp2;
                temp1.setNext(temp3);
                head1 = temp3;
                break;
            }
        }
        this.displayList(Head1); // This one goes in to a infinite loop..
        this.displayList(head2);

    }

}

下面是我的主课

public class main {

    public static void main(String[] args) {



        CLinkedList list = new CLinkedList();

        list.insertLast(10);
        list.insertLast(20);
        list.insertLast(30);
        list.insertLast(40);

        CLLNode head = list.getHead();

        CLLNode head1 = null;
        CLLNode head2 = null;

        list.splitList(head,head1,head2);



    }

}

我相信我能够成功拆分列表，但由于某种原因，当我显示新拆分的列表时，它会进入无限循环。我不确定为什么，如果有人可以指出我的错误或提出修复建议，我将不胜感激。

Answer 1

我不知道你的拆分操作是如何工作的，但有一种非常简单的方法可以将循环列表拆分为两个循环列表。现在我们先不要担心偶数/奇数的问题，考虑一下如果交换循环列表中两个不同节点的下一个指针会发生什么。您会得到两个循环列表(很整洁，对吧？)。

现在要拆分列表，首先统计列表中的项数(记为n)，并将位置0(第一个节点)节点的下一个指针与位置n/2节点的下一个指针交换(你必须按照下一个指针找到这个节点)。如果计数为偶数，则将列表拆分为两个长度为偶数的列表，如果计数为奇数，则将列表拆分为两个长度分别为奇数/偶数的列表。于是找到这两个节点，交换它们的next指针，赋值给head1和head2。

您可能希望单独处理只有一个节点或列表为空的情况。

在一张纸上试一试，看看它是否真的有效。