循环链表的逻辑

Question

循环链表的逻辑

3

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
          ListNode slow = head;
          ListNode fast = head.next;

          while((slow != null) && (fast != null) && (slow.next != null) && (fast.next != null)){
            if(slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;

          }

          return false;
    }
}

为了检测循环链表，我们使用两个指针技术，即慢指针和快指针。

我的问题是：如果列表是循环列表，我如何知道这些指针一定会在某个点相交？

- user7487099

顺便说一下，在循环链表中不需要两个指针，它主要用于实现队列和斐波那契堆。当您到达开始的第一个节点时停止遍历。 - Porkko M

1

@PorkkoM 这个问题不是关于使用循环链表实现的链表，而是关于检测非循环链表中的损坏链。 - Andreas

关于复杂性，为什么不同时使用链表和集合？在链表中保持项目的顺序，并在索引结构中跟踪重复项（循环）。那么为什么不使用已经存在的LinkedHashSet<E>呢？它已经被实现和测试过了，如果您想添加任何自定义行为（例如在add()上抛出异常而不是返回false），则可以从中继承。 - andreim

1

@andrei-macarie 两指针方法的一个优点是它不需要额外的内存（除了存储两个指针:-)）。此外，它还可以在O(n)的时间内找到答案，通过快指针与慢指针相交（检测出循环），或者快指针到达列表的末尾（没有循环）。 - danbanica

@qwertyman 我明白了，所以这个问题是关于 - 我更关心内存而不是性能，复杂度不超过O(n)。因此，该算法将用于有限数量的元素，无论如何都会消耗较少的内存，但对于物联网时代，在廉价设备上可能是值得的。现在我明白了 :) - andreim

4个回答

2

证明并不像看起来那么显然。实际上，稍微改变一下可以使快指针更快，例如使用fast = fast.next.next.next，那么算法就不能保证可行了。重要的是两个指针的相对速度。在标准情况下，相对速度为2-1=1，这意味着每一步快指针都会靠近慢指针一个单位。通过这种方式，可以保证快指针会追上慢指针而不会跳过它。否则，例如如果相对速度为3-1=2，则它们可能永远不会相交。如果我们从指针之间有奇数距离开始，并且循环长度是偶数，则会发生这种情况。在这种情况下，距离始终保持奇数（因此永远不会为零）。

为了清楚地表明，如果不注意速度差异，则指针可能不会相交，请考虑速度为3的快指针和速度为1的慢指针，在标记为0、1、2、3的4个节点的循环中运行，形成一个像这样的循环0-> 1-> 2-> 3-> 0。

假设最初慢指针在节点0处，快指针在节点1处。（请注意，这不是一个强假设，并且可能无法通过不同的初始化策略来缓解——无论初始化方法如何，可能存在一些附加节点在图中，不是循环的一部分，使得一旦它们都到达循环，指针可以处于任意位置）。

经过k步骤后，慢指针将位于节点k mod 4。快节点将位于节点（1 + 3k）mod 4。假设有一个k，使得快指针和慢指针在同一位置，这意味着（1 + 3k）mod 4 = k mod 4，即（1 + 2k）mod 4 = 0。但左边是奇数，因此不能为零。因此，假设指针可以指向同一个节点会导致矛盾。

- danbanica

0

嗯，正如Andreas所提到的，看看手表，但如果还是不明白，可以尝试使用this进行帮助。

另外，你可以简化一下你的代码：

public boolean isCyclic(Node first) {
    if(first == null) {
      return false;
    }
    Node fast = first;
    Node slow = first;
    while(fast.getNext() != null && fast.getNext().getNext() != null) {
      slow = slow.getNext();
      fast = fast.getNext().getNext();
      if(slow == fast) {
        return true;
      }
    }
    return false;
}

从http://codecramp.com/linked-list-loop-detection/复制的代码

我认为你应该用head而不是head.next来初始化你的fast指针。

- EMM

-1

以下是C语言中循环链表的完整实现：

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
void insert(struct node** head,int ele){
struct node* temp = (struct node*)malloc(sizeof(struct node));
struct node* ptr;
temp->data = ele;
temp->next = temp;
if(*head == NULL){
    *head = temp;
}else{
    ptr = *head;
    while(ptr->next != *head){
        ptr = ptr->next;
    }
    ptr->next = temp;
    temp->next = *head;
}
}
void deleteLastEle(struct node** head){
struct node* current = *head;
struct node* pre = *head;
while(current->next != *head){
    pre = current;
    current = current->next;
}
pre->next = current->next;
free(current);
}
void deleteAtPos(struct node** head,int pos){
struct node* current = *head;
struct node* pre = *head;
for(int i=0;i<pos-1;i++){
    pre = current;
    current = current->next;
}
pre->next = current->next;
free(current);
}
void deleteFirst(struct node** head){
struct node* current = *head;
struct node* temp = *head;
while(current->next != *head){
    current = current->next;
}
current->next = (*head)->next;
*head = (*head)->next;
free(temp);
}
printCLL(struct node** head){
struct node* ptr = *head;
do{
    printf("%d ",ptr->data);
    ptr = ptr->next;
}while(ptr != *head);
printf("\n");
}
// main() function.
int main(void) {
struct node* head = NULL;
for(int i=0;i<5;i++){
    //function to insert elements in linked list
    insert(&head,i);
}
printf("inseted linkedlist: \n");
//print the content of linked list.
printCLL(&head);

//function to delete last element
deleteLastEle(&head);
printf("after deleting last element: \n");
printCLL(&head);

//function to delete element at pos 3.
deleteAtPos(&head,3);
printf("after deleting at pos 3: \n");
printCLL(&head);

//function to delete first element of linkedlust
deleteFirst(&head);
printf("after deleting first element: \n");
printCLL(&head);
return 0;
}

这些是输出结果：

inseted linkedlist: 
0 1 2 3 4 
after deleting last element: 
0 1 2 3 
after deleting at pos 3: 
0 1 3 
after deleting first element: 
1 3

- Abdul Azeem

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andreas · Accepted Answer

看一下手表。那是一个数字1到12的循环列表，然后回到1。

大指针移动得快，小指针移动得慢，两者朝着同一个方向移动，并从同一点开始（顶部=12）。

由于列表（边缘）是循环的，大指针最终会追上小指针。速度差异决定了追上的速度，但它会追上。如果它追上了，那么这个列表必须是循环的。

如果它没有追上，但到达了列表的末尾，则该列表不是循环的。

即使列表没有回到开头，例如如果12回到9，快速指针仍将保持循环，直到小指针进入圆圈，然后快速指针最终会追上小指针。

好的，对于最后一部分，手表的图像不好，但我希望你能理解重点。