快慢指针

问题描述

快慢指针是一种在链表中使用两个移动速度不同的指针来解决问题的技术。
通常，快指针每次移动两步，慢指针每次移动一步。

环形检测

算法思想

使用快慢指针在链表上移动
如果存在环，两个指针一定会相遇
相遇后，将一个指针移到起点，两个指针同速前进
再次相遇的点即为环的入口

代码实现

c++
java
python

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;
        
        // 快慢指针找相遇点
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                // 找环的入口
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        
        return nullptr;
    }
};

class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        
        // 快慢指针找相遇点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 找环的入口
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        
        return null;
    }
}

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None
        
        # 快慢指针找相遇点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                # 找环的入口
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        
        return None

链表中点

算法思想

快指针每次移动两步，慢指针每次移动一步
当快指针到达末尾时，慢指针在中点位置
对于偶数长度链表，慢指针在中间偏左位置

代码实现

c++
java
python

ListNode* findMiddle(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

class Solution {
    public ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

class Solution:
    def findMiddle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

倒数第K个节点

算法思想

快指针先走k步
然后快慢指针同速前进
快指针到达末尾时，慢指针在倒数第k个位置

代码实现

c++
java
python

ListNode* findKthFromEnd(ListNode* head, int k) {
    if (!head) return nullptr;
    
    ListNode *slow = head, *fast = head;
    while (k-- && fast) {
        fast = fast->next;
    }
    if (k >= 0) return nullptr;  // k大于链表长度
    
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}

class Solution {
    public ListNode findKthFromEnd(ListNode head, int k) {
        if (head == null) return null;
        
        ListNode slow = head, fast = head;
        while (k > 0 && fast != null) {
            fast = fast.next;
            k--;
        }
        if (k > 0) return null;  // k大于链表长度
        
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

class Solution:
    def findKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        
        slow = fast = head
        # 快指针先走k步
        for _ in range(k):
            if not fast:
                return None  # k大于链表长度
            fast = fast.next
        
        # 快慢指针同速前进
        while fast:
            slow = slow.next
            fast = fast.next
        
        return slow

时间复杂度分析

算法时间复杂度空间复杂度

环形检测	$\mathcal{O}(n)$	$\mathcal{O}(1)$
中点查找	$\mathcal{O}(n)$	$\mathcal{O}(1)$
倒数第K个	$\mathcal{O}(n)$	$\mathcal{O}(1)$
链表相交	$\mathcal{O}(n)$	$\mathcal{O}(1)$

应用场景

链表环路检测
链表中点查找
链表倒数第k个节点
链表重排列
链表相交判断

注意事项

空链表的处理
单节点链表的处理
快指针的边界检查
k值的合法性检查
环的长度计算

06.01_快慢指针

快慢指针

问题描述

环形检测

算法思想

代码实现

链表中点

算法思想

代码实现

倒数第K个节点

算法思想

代码实现

时间复杂度分析

应用场景

注意事项

全站热榜

创作者周榜