K个一组翻转链表

1、题目

图1

2、题解

局部反转链表

根据题目要求，我们可以将改问题分解成一个个局部反转链表。需要将链表节点按k个一组分组，使用一个指针head依次指向每组的头节点，该指针每次向前移动k步，直到结尾，对于每个分组，判断分组长度是否大于等于k，是则翻转，不是就不需要。

• 对于每一个子链表，除了翻转链表本身外，还需要将子链表的头部和上一个子链表尾部链接，将尾部与下一个子链表头部链接。因此，在翻转完链表后，需要得到子链表的头尾节点，以及上、下一个的子链表的头尾节点。
• 对于第一个子链表，我们可以设立一个哨兵节点与头节点链接。最后返回结果返回该哨兵节点的下一个即可。

# 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]:
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        while head:
            tail = pre

            for i in range(k):
                tail =tail.next
                if not tail:
                    return dummy.next
            nex = tail.next
            head, tail = self.reverseList(head,tail)
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        return dummy.next
            
    def reverseList(self, head, tail):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p 
            p =nex
        return tail, head