每日一道算法题：环形链表详解

2023年 7月 30日 74点热度 0人点赞 0条评论

一、环形链表的定义和特点

1. 环形链表的概念

环形链表是一种特殊的链表，它的最后一个节点指向头节点，形成一个环。通常情况下，链表中的每个节点都有一个指针指向下一个节点。但在环形链表中，最后一个节点的指针指向头结点，达到了闭合的效果。

2. 环形链表的特点

环形链表有以下特点：

最后一个节点指向头结点，形成一个环
遍历时需要判断节点是否为空或是否遍历完整个链表，避免死循环
插入、删除、查询等操作需要注意环的特殊性质

二、环形链表的创建和操作

1. 创建环形链表的方法

创建环形链表的方法和单链表类似，只需将最后一个节点的指针指向头结点即可。下面是JAVA代码示例：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class CircularLinkedList {
    ListNode head; // 头节点

    // 创建环形链表
    public void createCircularList(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        head = new ListNode(nums[0]);
        ListNode cur = head;
        for (int i = 1; i &lt; nums.length; i++) {
            ListNode newNode = new ListNode(nums[i]);
            cur.next = newNode;
            cur = cur.next;
        }
        cur.next = head; // 最后一个节点指向头节点，形成环
    }
}

2. 插入、删除、查询环形链表节点的方法

环形链表节点的插入、删除和查询方法与单链表类似，只需注意环的特殊性质即可。下面是JAVA代码示例：

// 插入节点
public void insertNode(int index, int val) {
    if (index &lt; 0) {
        return;
    }
    ListNode cur = head;
    for (int i = 0; i &lt; index - 1; i++) {
        cur = cur.next;
    }
    ListNode newNode = new ListNode(val);
    newNode.next = cur.next;
    cur.next = newNode;
}

// 删除节点
public void deleteNode(int index) {
    ListNode cur = head;
    if (index == 0) {
        while (cur.next != head) {
            cur = cur.next;
        }
        cur.next = head.next;
        head = head.next;
    } else {
        for (int i = 0; i &lt; index - 1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
}

// 查询节点
public ListNode getNode(int index) {
    int count = 0;
    ListNode cur = head;
    while (cur != null &amp;&amp; count &lt; index) {
        cur = cur.next;
        count++;
    }
    return cur;
}

3. 遍历环形链表的方法

遍历环形链表需要注意两点：

因为环的特殊性质，遍历时需要判断节点是否为空或是否遍历完整个链表，避免死循环

由于环的存在，需要增加一个判断条件，避免重复访问头结点。下面是JAVA代码示例：

// 遍历环形链表
public void printList() {
ListNode cur = head;
while (cur != null &amp;&amp; cur.next != head) {
    System.out.print(cur.val + &quot; &quot;);
    cur = cur.next;
}
System.out.print(cur.val); // 输出最后一个节点的值
}

三、判断环形链表是否存在环

1. 哈希表法

哈希表法是判断环形链表是否存在环的一种简单方法，基本思路是遍历链表，将每个节点放入哈希表中，如果遍历到的节点已经在哈希表中出现过，则说明存在环。下面是JAVA代码示例：

// 判断环形链表是否存在环（哈希表法）
public boolean hasCycle() {
    if (head == null) {
        return false;
    }
    Set&lt;ListNode&gt; hashSet = new HashSet&lt;&gt;();
    ListNode cur = head;
    while (cur != null) {
        if (hashSet.contains(cur)) {
            return true;
        } else {
            hashSet.add(cur);
            cur = cur.next;
        }
    }
    return false;
}

2. 快慢指针法

快慢指针法是判断环形链表是否存在环的一种高效方法，基本思路是设置两个指针，一个指针（快指针）每次跳两步，另一个指针（慢指针）每次跳一步，如果存在环，快指针和慢指针一定会相遇。下面是JAVA代码示例：

// 判断环形链表是否存在环（快慢指针法）
public boolean hasCycle() {
    if (head == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

四、解决环形链表中的问题

1. 环形链表的入口节点

假设环的长度为n，慢指针走了k步，那么快指针走了2k步。设起点到环入口的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z，则有以下公式：

k = x + n * m + y
2k = x + n * p + y 其中m和p分别表示慢指针和快指针走过的环的圈数。把公式中的k代入另一个公式，得到以下公式：

x = (p - 2m) * n - y 把快指针重新指向头节点，两个指针重新走，每次走一步，相遇点就是环入口。下面是JAVA代码示例：

// 获取环形链表的入口节点
public ListNode getEntranceNode() {
if (head == null) {
    return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null &amp;&amp; fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
        break;
    }
}
if (fast == null || fast.next == null) {
    return null;
}
fast = head;
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
}
return slow;
}

2. 环形链表的长度

环形链表长度的计算和单链表有所不同。首先判断是否存在环，如果存在，则设置快慢指针走一圈，计算出两指针所走的步数n，环的长度就是n。下面是JAVA代码示例：

// 获取环形链表的长度
public int getLength() {
    if (head == null) {
        return 0;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null &amp;&amp; fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 存在环，计算环的长度
            int count = 0;
            do {
                slow = slow.next;
                fast = fast.next.next;
                count++;
            } while (slow != fast);
            return count;
        }
    }
    // 不存在环
    return 0;
}

3. 环形链表内的环的长度

环形链表内的环的长度可以通过先使用快慢指针法判断是否存在环，然后计算两个指针相遇的步数n，再通过步数计算出环的长度。下面是JAVA代码示例：

// 获取环形链表内的环的长度
public int getLoopLength() {
    if (head == null) {
        return 0;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null &amp;&amp; fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 存在环，计算环的长度
            int count = 0;
            do {
                slow = slow.next;
                fast = fast.next.next;
                count++;
            } while (slow != fast);
            return count;
        }
    }
    // 不存在环
    return 0;
}

4. 环形链表中的交叉点

可以将环形链表问题转化为两个单链表相交的问题。先使用快慢指针法判断是否存在环，如果存在，则找到环的入口节点。然后把环断开，将环入口节点的next指针置为null，得到两个单链表。最后使用两个指针分别遍历两个单链表，当两个指针相遇时，该节点即为相交点。下面是JAVA代码示例：

// 获取环形链表和普通链表的交叉节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode tailA = headA;
    while (tailA.next != null) {
        tailA = tailA.next;
    }
    tailA.next = headA; // 把A的尾节点接到A的头节点上，形成环
    ListNode slow = headB;
    ListNode fast = headB;
    while (fast != null &amp;&amp; fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        tailA.next = null; // 断开环，恢复A的尾节点
        return null;
    }
    slow = headB;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    tailA.next = null; // 断开环，恢复A的尾节点
    return slow;
}

5. 环形链表的反转

反转环形链表需要同时考虑链表和环的特殊性质。一般情况下，反转单链表的方法是使用三个指针，分别指向前、中、后三个节点，然后依次改变指针的指向。但是在环形链表中，需要先找到最后一个节点，然后将其next指针指向头节点，形成环，在执行反转过程。最后再把反转后的链表断开，将最后一个节点的next指针指向null。下面是JAVA代码示例：

// 反转环形链表
public void reverseList() {
    if (head == null || head.next == null) {
        return;
    }
    ListNode cur = head;
    while (cur.next != head) { // 找到最后一个节点
        cur = cur.next;
    }
    ListNode prev = null;
    ListNode start = head;
    ListNode next = head.next;
    do {
        start.next = prev;
        prev = start;
        start = next;
        next = next.next;
    } while (start != head);
    start.next = prev; // 最后一个节点指向原来的头节点
    head = prev; // 头节点指向原来的尾节点
    cur.next = head; // 最后一个节点指向头节点，形成环
}

五、算法优化和复杂度分析

1. 哈希表法的时间和空间复杂度分析

哈希表法的时间复杂度为O(n)，其中n为链表节点个数。空间复杂度也为O(n)，需要使用哈希表存储节点。

2. 快慢指针法的时间和空间复杂度分析

快慢指针法的时间复杂度为O(n)，其中n为链表节点个数。空间复杂度为O(1)，只需要使用两个指针。

六、扩展点

1. 环形链表在实际问题中的应用

环形链表广泛应用在循环队列、缓冲区等领域。例如音频播放器中，往往需要对音频文件进行缓存，使用环形链表可以很方便地实现循环缓存。

2. 面试中常见的环形链表问题

在面试中，环形链表问题经常出现。例如，是否存在环、环的长度、如何找到环的入口节点以及如何找到两个链表的交叉节点等。这些问题考察对链表的理解和掌握程度，需要对环形链表的特殊性质有深入的了解。

七、总结

1. 环形链表的优势和局限性

环形链表的优势是容易实现循环操作，适用于循环队列、缓冲区等应用场景。但是它的局限性在于插入、删除、查询等操作需要考虑环的特殊性质，容易出错，需要注意一些技巧和实现细节。

2. 不同解法的优缺点

哈希表法是一种简单的解法，但是需要额外的空间来存储哈希表，不适用于空间受限的场景。快慢指针法比较高效，不需要额外的空间，但需要考虑边界情况，如链表为空或长度为1等。

3. 环形链表问题的实现技巧和注意点

解决环形链表问题需要注意以下几点：

插入、删除、查询等操作需要考虑环的特殊性质。
遍历链表时需要判断节点是否为空或是否遍历完整个链表，避免死循环。

本作品采用知识共享署名 4.0 国际许可协议进行许可