【2025-02-28】基础算法：快慢指针

用户11029137

发布于 2025-03-01 22:00:42

6000

代码可运行

文章被收录于专栏：编程学习

运行总次数：0

代码可运行

📝前言说明： ●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频 ●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。 ●文章中的理解仅为个人理解。 ●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

一，视频题目

876. 链表的中间结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

141. 环形链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 慢的一定会追上快的
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next # 因为这里要对fast.next操作，所以循环条件里面也需要确保fast.next 不为空
            if fast == slow:
                return True
        return False

142.环形链表 II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: # 相遇了
                while slow != head:
                    head = head.next
                    slow = slow.next
                return slow
        return None

143. 重排链表

把问题看成： 1，先找到中间节点，链表分成两个链表 2，把后半段链表反转 3，把后半段链表插入第一段链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def findMid(self, head): # 若链表长度为偶数：第一段应该会比第二段多一个元素（第一段的末尾还会指向mid元素）
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre # 返回反转后的链表的头结点

    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        mid = self.findMid(head)
        head2 = self.reverseList(mid)
        while head2.next:
            nxt_head1 = head.next
            nxt_head2 = head2.next
            head.next = head2
            head2.next = nxt_head1
            head = nxt_head1
            head2 = nxt_head2

二，课后作业

234. 回文链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def Mid(self,head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(slef, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre # 最后pre指向原链表的最后一个节点
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 反转 + 逐个判断
        # 1，先找到中间节点;2, 反转后半部分3, 再逐个比较
        head2 = self.Mid(head)
        head2 = self.reverseList(head2)
        # head2 从最往前，head从前往后
        while head2:
            if head2.val != head.val:
                return False
            head = head.next
            head2 = head2.next
        return True

2130. 链表最大孪生和

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def Mid(self,head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(slef, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def pairSum(self, head: Optional[ListNode]) -> int:
        # n-1-i 其实就是从后往前数
        head2 = self.Mid(head)
        head2 = self.reverseList(head2)
        mx = 0
        while head and head2:
            s = head.val + head2.val
            if s > mx:
                mx = s
            head = head.next
            head2 = head2.next
        return mx

总结： 1，快慢指针可以用于找中间节点 2，快慢指针可以用于相遇问题，然后通过数学推导分析移动路程关系 3，对于对称型列表，可以先找到中间节点，然后反转后半段链表注意：找到中间节点后反转的链表，第一段在链表元素为偶数时，比第二段长（藕断丝连）

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

算法