确定循环双向链表的头部是否是“跳跃”循环的一部分

There's a doubly linked list which is also circled (i.e., the last node's next pointer points to the head of the list and the head's prev pointer points to the last node).

还有一个双向链表,它也被圈出(即,最后一个节点的下一个指针指向列表的头部,而头部的prev指针指向最后一个节点)。

The data in each node is an integer.

每个节点中的数据是整数。

A jump in a circular list is defined as follows for a node p :

对于节点p,循环列表中的跳转定义如下:

if p.data is positive, we move p.data times using the next pointer

如果p.data是正数,我们使用下一个指针移动p.data次

if p.data is negative, we move p.data times using the prev pointer

如果p.data为负数,我们使用prev指针移动p.data次

if p.data is 0, we don't move at all.

如果p.data为0,我们根本不动。

I need to write a method that receives a pointer to the head of the list as a parameter and returns true if there's a jump path that starts and ends at the head node.

我需要编写一个接收指向列表头部的指针作为参数的方法,如果有一个在头节点开始和结束的跳转路径,则返回true。

An example list:

示例列表:

 node | data | next | prev
------|------|------|------
   0  |   2  |   1  |   5
   1  |  14  |   2  |   0
   2  |  -5  |   3  |   1
   3  |   1  |   4  |   2
   4  |  -4  |   5  |   3
   5  |   1  |   0  |   4

For this list, the method should return true. Starting at the head (node 0), we move forward twice to node 2, then back 5 times to node 3, forward once to node 4, and finally back 4 times, returning to node 0:

对于此列表,该方法应返回true。从头部(节点0)开始,我们向前移动两次到节点2,然后向后移动5次到节点3,向前移动到节点4,最后返回到4次,返回到节点0:

 node  | jumps | next node
-------|-------|-----------
   0   |   2   |     2
   2   |  -5   |     3
   3   |   1   |     4
   4   |  -4   |     0

My main problem is when I should return false.

我的主要问题是当我应该返回假。

This is not homework (I'm working on different exercises in order to prepare my self for an exam)

这不是家庭作业(我正在做不同的练习,以便为考试做好准备)

2 个解决方案

#1

There are plenty of ways to do it.

有很多方法可以做到这一点。

For example you can return false if you didn't get back to the head after n jumps (n being the length of the list) as it means you are looping in another part of the list.

例如,如果在n次跳转后没有回到头部(n是列表的长度),则可以返回false,因为这意味着您正在循环列表的另一部分。

You can also mark the visited nodes and return false if you visit twice any node (apart from the head).

如果您访问任何节点两次(除了头部),您还可以标记受访节点并返回false。

You also have to return false directly if you reach a 0 which is not the head of the list.

如果达到0而不是列表的头部,则还必须直接返回false。

#2

-1

First decide when the method will stop i.e. what is the halting condition as given your question above again the method will start moving and will return to 2 and this process will continue ever. The only halting condition specified above is the occurrence of zero in the zero otherwise this program will never halt.

首先确定方法何时停止,即什么是停止条件,再次给出上述问题,方法将开始移动并返回2,此过程将继续。上面指定的唯一暂停条件是零中出现零,否则该程序将永远不会停止。

If coming to the head node can also result in halting of the program then the code can be completed in this way:

如果到头节点也可能导致程序暂停,那么代码可以这样完成:

findHead(head,originalHead,calledCount){
    if(originalHead==null)
    {
        return false;
    }
    else if (head==originalHead && calledCount>1) 
    /*If while roaming gets to the head then returns true but except the first time where the head will always be equal to original head */
    {                   
        return true;
    }
    else {
        p=head;
        if(p.data>0)
        {
            steps=p.data;
            while(steps>0)
            {
                p=p->next;
                steps--;
            }
            findHead(p,originalHead,calledCount);
        }
        else if(p.data<0)
        {
            steps=p.data;
            while(steps<0)
            {
                p=p->prev;
                steps++;
            }
            findHead(p,originalHead,calledCount);
        }
        else    // If obtained 0 in the list
        {
            if (p==originalHead)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    calledCount++;
}

#1