【基础算法精讲-学习记录】快慢指针

视频学习记录

https://www.bilibili.com/video/BV1KG4y1G7cu

• 快慢指针遍历链表作为代码只有下面几行：

def getMid(head):
    slow, fast = head, head 
    while fast and fast.next:
        fast = fast.next.next 
        slow = slow.next 
    return slow 

• 其中最核心的在于，循环条件中，fast是链表长度为偶数停，fast.next则是在链表长度偶数停，不用死记硬背的。用长度为2和3的链表自己就能推出来。

• 对于一些诡异的环形链表II这种题目，放宽心，这是面试记的，自己要能推出来，当初高考数学就不是这个分了。

例题和课后作业代码记录

876. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

# 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]:
        # 时间On，空间O1
        # 当慢指针指向中间节点时，若链表长度奇数，则快指针指向最后一个，若为偶数则置空
        # dummy = ListNode(0, head) # 如果要中间偏前的就从dummy出发
        l, r = head, head
        while r and r.next:
            l = l.next 
            r = r.next.next 
        return l

141. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

# 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:
        # 时间On，环内应该还有点，不过也和n有关，空间O1
        l, r = head, head 
        while r and r.next:
            l = l.next 
            r = r.next.next 
            if l == r:
                return True
        return False

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

# 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=a+b,fast=a+b+k*(b+c)，推到a=c+(k-1)(b+c)
        # 也就是slow从相遇点出发，和head一起在环入口相遇
        # 时间On，空间O1
        slow, fast = head, head 
        while fast and fast.next:
            fast = fast.next.next 
            slow = slow.next 
            if fast == slow: # 必定有环
                while slow != head:
                    slow = slow.next 
                    head = head.next 
                return slow
        return None

143. 重排链表

https://leetcode.cn/problems/reorder-list/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 时间On，空间O1
        l, r = head, head # 先找到中间偏右的点
        while r and r.next:
            l = l.next 
            r = r.next.next 
        
        pre, cur = None, l # 将右侧反转
        while cur:
            nxt = cur.next 
            cur.next = pre 
            pre = cur 
            cur = nxt 
        

        l = head
        r = pre 
        # print("pre", pre)
        while r: # 左右指针重排
            nxt = l.next 
            nxt2 = r.next 

            l.next = r 
            r.next = nxt 

            l, r = nxt, nxt2

234. 回文链表

https://leetcode.cn/problems/palindrome-linked-list/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 一次遍历链表，反转后半段，再遍历一半链表，无额外存储空间
        # 时间On，空间O1
        l, r = head, head 
        while r and r.next:
            r = r.next.next 
            l = l.next 

        pre, cur = None, l 
        while cur:
            nxt = cur.next
            cur.next = pre 
            pre = cur 
            cur = nxt 
        
        while pre:
            if pre.val != head.val:
                return False 
            pre, head = pre.next, head.next 
        
        return True

2130. 链表最大孪生和

https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/description/

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

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

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # 时间：取中点遍历了一边，反转遍历一半，找孪生和遍历一半，On
        # 空间：没有额外变量，O1
        mid = getMid(head)
        r = reverseList(mid)
        ans = 0
        while r:
            cur = head.val + r.val 

            if cur > ans:
                ans = cur 

            head, r = head.next, r.next 
        return ans