[数据结构与算法]K个一组翻转链表 一种解法（Python）

分组 + 子链表翻转 时间复杂度 O(N)

# 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]:
        if not head or not head.next:
            return head
        # k为1无需任何操作 直接返回
        if k == 1:
            return head
        dummy_node = ListNode()
        dummy_node.next = head
        pre = dummy_node
        while head:
            tail = pre
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy_node.next
            tail_next = tail.next
            head, tail = self.reverse(head, tail)
            # 反转后的子链表和原链表相连接
            pre.next = head
            tail.next = tail_next
            pre = tail
            head = pre.next
        return dummy_node.next

    def reverse(self, head: ListNode, tail: ListNode):
        '''
        对局部子链表进行反转
        0 -> 1 -> 2 -> 3 -> 4
        0 -> 3 -> 2 -> 1 -> 4 
        '''
        prev = tail.next
        p = head
        while prev != tail:
            p_next = p.next
            p.next = prev
            prev = p
            p = p_next
        return tail, head

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖