链表有无环

发表于 | 分类于 ， |
字数统计: 767

在链表中，可以用**”快慢指针”**解决大多数问题，但根据问题的不同，快慢指针的步长及边界的处理要多加小心

其他解决方法例如：

  • 虚拟头节点
  • 双指针
  • 双指针＋临时指针

链表问题中，一定不能丢失指针，或对空指针进行异常操作；有pre->next->next的操作时，一定要判断存不存在这个位置；pre->next同理，可能在pre处就为NULL了

这里以Leetcode题单141和142环形链表为例，利用快慢指针代码解决这两个问题

141：给一个链表的头节点，判断这个链表是不是环形链表，返回值为true或false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//此题中，慢指针的步长为1，快指针的步长为2
//首先要判断此链表是否为空，是否只有一个节点等特殊情况
bool hasCycle(ListNode *head){
    bool abc = false; //abc是此函数的返回值
    //此链表是否为空，是否只有一个节点且不是环形链表；因为快指针的步长为2，所以要判断链表有没有至少3个节点，避免在给fast指针初始化时出现空指针异常操作，导致编译失败
    if(head == NULL || head->next == NULL || head->next->next == NULL)
        return abc;
    
    //初始时，slow指针从head开始向前走一步，fast走两步
    ListNode *slow = head->next , *fast = head->next->next;
    //此链表只有两种可能：不是环形，是环形；fast或者fast->为NULL，则不是；当slow和fast能遇到，则判断是环形链表
    while(fast != NULL && fast->next != NULL && fast->next->next != NULL && slow != fast){
        slow = slow->next;
        fast = fast->next->next;
    }
    //while退出时，如果slow和fast相遇，这就是环；其他情况退出时，这都不是一个环
    if(slow == fast)
        abc = true;
    
    return abc;
    
}

142：给一个链表的头节点，判断这个链表是不是环形链表，如果是环形链表，返回入环的第一个节点；如果不是环形链表，返回null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//142和141的不同在于：142在141的基础上需要找到入环的位置，前面判断是否为环的操作是一样的
/*当此链表是环的时候，slow会和fast会在环上相遇，但是否是在入环的位置相遇是不一定的。此时需要将fast定位回开头处，然后让slow和fast都一步一步向前走，这次slow和fast一定会在入环处相遇*/

ListNode *detectCycle(ListNode *head){
    //对head做一个初步的判断
    if(head == NULL || head->next == NULL || head->next->next == NULL)
        return NULL;
    
    //判断此链表是不是一个环
    ListNode *slow = head->next , *fast = head->next->next;
    while(fast != NULL && fast->next != NULL && fast->next->next != NULL && slow != fast){
        slow = slow->next;
        fast = fast->next->next;
    }
    //当if中的条件成立时，这是一个环，接下来找环的入口
    if(slow == fast){
        fast = head;
        while(fast != slow){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
    else
        return NULL;
}