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
