【基础算法精讲-学习记录】反转链表

视频学习记录

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

• 链表反转小结下来就三点，首先理解下面这个 pre 和 cur 是怎么让一个链表反转过来的。

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

• 然后，了解到这样反转后，pre 指的是反转后链表的第一个节点，同时也是原来位置上那一段的最后一个，而 cur 在下一段的第一个（如果没有下一段就是空嘛）
• 最后，如果需要在一个链表上实现分段多次反转，每一小段的反转前的那个节点可以命名为 p0，负责将上一段的最后与下一段刚反转的头衔接。p0 下一个就是 pre，为了避免只反转 1 个元素链表特殊情况让 p0 和 pre 一个位置，可以引入哨兵节点。

例题和课后作业代码记录

206. 反转链表

https://leetcode.cn/problems/reverse-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 reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 时间 On，空间 O1
        # 这个写法下，pre会是原链表视角下反转部分的最后一个，cur在下一段第一个
        pre, cur = None, head 
        while cur:
            nxt = cur.next 
            cur.next = pre 
            pre = cur 
            cur = nxt 
        return pre

92. 反转链表 II

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        p0 = dummy
        for _ in range(left-1):
            p0 = p0.next 

        pre = p0.next 
        cur = pre.next 
        
        l = right-left

        while l>0:
            nxt = cur.next
            cur.next = pre 
            pre = cur 
            cur = nxt 
            l -= 1

        p0.next.next = cur
        p0.next = pre

        return dummy.next

25. K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 时间On，空间O1
        # 重点是p0的更新需要注意，要更新为反转段原来的第一个位置，也就是反转后的最后一个位置
        l = 0
        p0 = head 
        while p0:
            l += 1
            p0 = p0.next 
        c = l // k 
        # print(c, l)
        dummy = ListNode(next = head)
        p0 = dummy
        for _ in range(c):
            pre = p0.next 
            cur = pre.next 
            for i in range(k-1):
                nxt = cur.next 
                cur.next = pre
                pre = cur 
                cur = nxt 
            nextp0 = p0.next
            nextp0.next = cur 
            p0.next = pre 
            p0 = nextp0 
        return dummy.next

24. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 时间On，空间O1
        # 重点是p0的更新需要注意，要更新为反转段原来的第一个位置，也就是反转后的最后一个位置
        l = 0
        p0 = head 
        while p0:
            l += 1
            p0 = p0.next 
        c = l // 2 
        dummy = ListNode(next = head)
        p0 = dummy
        for _ in range(c):
            pre = p0.next 
            cur = pre.next 

            nxt = cur.next 
            cur.next = pre
            pre = cur 
            cur = nxt 
            
            nextp0 = p0.next
            nextp0.next = cur 
            p0.next = pre 
            p0 = nextp0 
        return dummy.next

445. 两数相加 II

https://leetcode.cn/problems/add-two-numbers-ii/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def reverseList(l):
    pre, cur = None, l 
    while cur:
        nxt = cur.next 
        cur.next = pre 
        pre = cur 
        cur = nxt 
    return pre 

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 时间On，空间On，不过如果直接在l1或者l2上加数字，空间就O1了
        l1 = reverseList(l1)
        l2 = reverseList(l2)
        
        ans = ListNode() 
        cur = ans
        over = False
        while l1 or l2 or over:
            cur.next = ListNode(0, None)
            cur = cur.next
            if l1:
                cur.val += l1.val 
                l1 = l1.next
            if l2:
                cur.val += l2.val 
                l2 = l2.next

            if over:
                cur.val += 1
                over = False 

            if cur.val >= 10:
                over = True 
                cur.val -= 10

        ans.next = reverseList(ans.next) # 如果用头插法构建这个结果链表，就可以少一次反转
        return ans.next

2816. 翻倍以链表形式表示的数字

https://leetcode.cn/problems/double-a-number-represented-as-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 reverseList(l):
    pre, cur = None, l 
    while cur:
        nxt = cur.next 
        cur.next = pre 
        pre = cur 
        cur = nxt 
    return pre 

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 时间On，空间On，不过如果直接在源链表上操作数字，空间就O1了
        # 不过由于本题不会连续进位，所以其实另一种方法只考虑值大于4的节点前面操作这种更简单快速
        head = reverseList(head)
        ans = ListNode()
        carry = False 

        while head or carry:
            cur = ListNode(0, ans.next)
            if head:
                cur.val += head.val * 2
                head = head.next 

            if carry:
                carry = False 
                cur.val += 1
            if cur.val >= 10:
                cur.val -= 10
                carry = True 
            
            ans.next = cur

        return ans.next