判断单链表是否有环并找到环的入口等问题
判断单链表是否有环并找到环的入口等问题
假设一个单链表有环,他就是下面的这种情况:
我们有下面几个问题:
1.给一个单链表,判断其中是否有环的存在;
2.如果存在环,找出环的入口点;
3.如果存在环,求出环上节点的个数;
4.如果存在环,求出链表的长度;
对于这些问题有一种方法就是使用一个指针,每次遍历一个的时候把这个节点的地址存到一个vector,下一个遍历的时候从vector中查找看是否存在,如果在指针为NULL之前,出现了在vector中的节点,则说明有环存在。且这个结点就是环的入口,求出两个地址中的间距就是个数,长度就是总长。这样的方法对于时间复杂度和空间复杂度都特别的大,方法是不可取的。
对于这些问题,我们应该用这样的办法解决:
1.判断时候有环(链表头指针为head)
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow,开始的时候两个指针都指向链表头head,然后在每一步操作中slow向前走一步即:slow = slow->next,而fast每一步向前两步即:fast = fast->next->next。由于fast要比slow移动的快,如果有环,fast一定会先进入环,而slow后进入环。当两个指针都进入环之后,经过一定步的操作之后,二者一定能够在环上相遇,并且此时slow还没有绕环一圈,也就是说一定是在slow走完第一圈之前相遇。证明可以看下图:
当slow刚进入环时每个指针可能处于上面的情况,接下来slow和fast分别向前走即:
if (slow != NULL && fast->next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
}
也就是说,slow每次向前走一步,fast向前追了两步,因此每一步操作后fast到slow的距离缩短了1步,这样继续下去就会使得 两者之间的距离逐渐缩小:...、5、4、3、2、1、0 -> 相遇。又因为在同一个环中fast和slow之间的距离不会大于换的长度,因此到二者相遇的时候slow一定还没有走完一周(或者正好走完以后,这种情况出现在开始的时候fast和slow都在环的入口处)。
下面给出问题1的完整代码:
typedef struct node{
char data ;
node * next ;
}Node;
bool exitLoop(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL&& fast != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
return true ;
}
return false ;
}
(重点注意fast != NULL和fast -> next != NULL的顺序 )
2,找出环的入口点:
如下:
从上面的分析知道,当fast和slow相遇时,slow还没有走完链表,假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步,则fast走了2s步,又由于
fast走过的步数 = s + n*r(s + 在环上多走的n圈),则有下面的等式:
2*s = s + n * r ; (1)
=> s = n*r (2)
如果假设整个链表的长度是L,入口和相遇点的距离是x(如上图所示),起点到入口点的距离是a(如上图所示),则有:
a + x = s = n * r; (3) 由(2)推出
a + x = (n - 1) * r + r = (n - 1) * r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出
a = (n - 1) * r + (L -a -x) (5)
集合式子(5)以及上图我们可以看出,从链表起点head开始到入口点的距离a,与从slow和fast的相遇点(如图)到入口点的距离相等。
因此我们就可以分别用一个指针(ptr1, prt2),同时从head与slow和fast的相遇点出发,每一次操作走一步,直到ptr1 == ptr2,此时的位置也就是入口点!
下面给出代码:
Node* findLoopStart(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast) break ;
}
if (slow == NULL || fast -> next == NULL) return NULL ; //没有环,返回NULL值
Node * ptr1 = head ; //链表开始点
Node * ptr2 = slow ; //相遇点
while (ptr1 != ptr2)
{
ptr1 = ptr1 -> next ;
ptr2 = ptr2 -> next ;
}
return ptr1 ; //找到入口点
}
3,如果存在环,求环上节点的个数:
记录下相遇节点存入临时变量tempPtr,然后让slow(或者fast,都一样)继续向前走slow = slow -> next;一直到slow == tempPtr; 此时经过的步数就是环上节点的个数;
代码:
typedef struct node{
char data ;
node * next ;
}Node;
int looghead(Node *head)
{
int tmp=0;
Node *fast, *slow,*tempPtr;
slow = head ;
fast = head ;
while (slow != NULL && fast != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
break ;
}
if (slow != fast)
return 0 ;
tempPtr= slow;
while (slow!=tempPtr )
{
slow = slow -> next ;
tmp++;
}
return tmp;
}
问题4是如果存在环,求出链表的长度:
我们可以这样求出整个链表的长度:
链表长度L = 起点到入口点的距离 + 环的长度r;
已经知道了起点和入口点的位置,那么两者之间的距离很好求了吧!环的长度也已经知道了,因此该问题也就迎刃而解了!