常用链表算法——快慢指针法

快慢指针法

1.引言

链表是一种常见的数据结构，用于存储数据元素的集合。与数组不同，链表中的每个元素都包含一个指向下一个元素的指针，这样就可以通过指针将所有元素连接起来，形成一个链式结构。

链表问题的常见性质包括：

• 1. 链表的插入和删除操作通常比较高效，时间复杂度为O(1)，因为只需要修改指针的指向。
• 2. 链表的访问操作相对较慢，时间复杂度为O(n)，因为需要从头节点开始逐个遍历到目标节点。
• 3. 链表可以动态地分配内存空间，不像数组需要预先定义大小。
• 4. 链表可以表示更复杂的数据结构，如栈、队列和图等。

2.快慢指针的思想

快慢指针法是一种常用的解决链表问题的算法思想。它的基本思想是使用两个指针，一个快指针和一个慢指针，它们以不同的速度遍历链表。

具体来说，快指针每次移动两步，而慢指针每次移动一步。通过这种移动方式，快指针相对于慢指针的速度是两倍。当快指针到达链表末尾时，慢指针正好指向链表的中点。

3.应用场景

• 1. 寻找链表的中点：在链表中找到中点是许多问题的关键步骤。通过使用快慢指针法，快指针可以更快地遍历链表，而慢指针则以较慢的速度遍历。当快指针到达链表末尾时，慢指针正好位于链表的中间位置。
• 2. 判断链表是否有环：快慢指针法也可以用于判断链表是否存在环。如果链表中存在环，那么快指针终究会追上慢指针并与其相遇。这是因为快指针每次移动两步，而慢指针每次移动一步，所以快指针会在环内多绕几圈，最终与慢指针相遇。
• 3. 解决其他问题：除了寻找中点和判断是否有环外，快慢指针法还可以应用于其他链表问题，如合并两个有序链表、判断链表是否交叉等。通过调整快慢指针的移动方式，我们可以灵活地解决各种链表问题。

4.示例代码

假设我们有一个链表，其节点定义如下：

class ListNode {
   
    int val;
    ListNode next;

    ListNode(int val) {
   
        this.val = val;
    }
}

现在，我们可以创建一个示例链表来演示如何使用双指针法找到链表的中点。假设链表的值为 1 -> 2 -> 3 -> 4 -> 5 -> null。

ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);

head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

接下来，我们使用双指针法找到链表的中点。

ListNode slow = head; // 慢指针每次移动一步
ListNode fast = head; // 快指针每次移动两步

while (fast != null && fast.next != null) {
   
    slow = slow.next; // 慢指针移动一步
    fast = fast.next.next; // 快指针移动两步
}

// 当循环结束时，慢指针指向链表的中点
System.out.println("链表的中点是：" + slow.val);

通过上述代码，我们使用快慢指针法找到了示例链表的中点，即节点 3。

注释解释：

1. 首先，我们初始化两个指针 slow 和 fast，它们都指向链表的头节点 head。
2. 在循环中，每次迭代时，慢指针 slow 移动一步，而快指针 fast 移动两步。
3. 循环条件是快指针 fast 不为空且快指针的下一个节点也不为空。这是为了确保在链表节点个数为偶数时，慢指针能够指向中点的前一个节点。
4. 当循环结束时，慢指针 slow 就指向链表的中点。

需要注意的是，如果链表有偶数个节点，那么此时 slow 指针指向的是中间偏左的节点。

总结：
通过使用双指针法，我们可以高效地找到链表的中点。在示例代码中，快慢指针的移动方式有助于我们在一次遍历中找到中点。这种方法的时间复杂度为 O(n/2)，即 O(n)。