【Leetcode刷题Python】25.K 个一组翻转链表

1 题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

2 解析

（1）方法一 用栈来实现逆转。新建一个虚拟链表的头结点，将逆转的链表存放到此链表上。 （2）方法二 用尾插法 （3）方法三 虚拟节点，顺序法

3 python实现

（1）方法一

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        
        dummy_node = ListNode()
        p = dummy_node
        while True:
            stack = []
            count_k = k 
            tmp = head
            while count_k and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count_k -=1
            # 后续不足k个，直接将尾部链接到新链表上，并退出循环
            if count_k:
                # 注意，链接是head链表，而不是tmp指针
                p.next = head
                break
            # 弹出栈，逆序
            while stack:
                p.next = stack.pop()
                p = p.next
            p.next = tmp
            # 让指针在上一轮的位置，继续遍历
            head = tmp 
        return dummy_node.next

（2）方法二

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
     dummy_node = ListNode(0)
     # 注意初始化头结点，是在原来的链表上操作
     dummy_node.next = head
     pre =dummy_node
     end = dummy_node
     while True:
         count_k = k 
         # 注意：循环的条件，有两个
         while count_k and end:
             end = end.next
             count_k -=1
         if not end:
             break
         # 这是新一轮的head链表
         head = pre.next
         while pre.next !=end:
             # 取出下一个节点
             curr = pre.next
             # pre与cur.next连接起来,此时curr(孤单)掉了出来
             pre.next = curr.next
             # 将尾巴剩下的链表与curr连接起来
             curr.next = end.next
             # 插在尾巴上
             end.next =  curr
         # pre和end同时指向到新head链表的第一个位置
         pre = head
         end = head
     return dummy_node.next

（3）方法三

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0,head)
        pre = dummy
        end = dummy
        while end.next:
            for _ in range(k):
                if not end:
                    break
                else:
                    end = end.next
            if not end:
                break
            next  = end.next
            end.next =None
            start = pre.next
            pre.next = None
            pre.next =self.reverseList(start)
            start.next = next
            pre =start
            end =start
        return dummy.next

    # def reverseList(self, head: ListNode) -> ListNode:
    #     if head ==None or head.next==None:
    #         return head
    #     curr = self.reverseList(head.next)
    #     head.next.next = head
    #     head.next = None
    #     return curr
    def reverseList(self, head: ListNode) -> ListNode:
        prev,curr = None,head
        while curr:
            # 小心这一步，别忘了
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev