k个一组翻转链表

基础概念

链表是一种线性数据结构，其中每个元素（节点）包含数据部分和指向下一个节点的指针。链表的最后一个节点指向空（NULL），表示链表的结束。

翻转链表是指将链表中的节点顺序颠倒过来，使得原来的尾节点变成头节点，原来的头节点变成尾节点。

k个一组翻转链表是指将链表每k个节点分为一组，对每组内的节点进行翻转，然后重新连接这些组。

类型

单链表：每个节点只有一个指向下一个节点的指针。
双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。

应用场景

实现栈和队列：链表可以用来实现栈（后进先出）和队列（先进先出）。
动态数据存储：当数据量不确定或频繁变化时，链表是一个很好的选择。
内存管理：链表常用于内存分配和管理。

示例代码

以下是一个用Python实现的k个一组翻转链表的示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    def reverseList(head, tail):
        prev, curr = tail.next, head
        while curr != tail.next:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

    dummy = ListNode(0)
    dummy.next = head
    groupPrev = dummy

    while True:
        kth = groupPrev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
        groupNext = kth.next
        newGroupHead = reverseList(groupPrev.next, kth)
        groupPrev.next.next = groupNext
        groupPrev.next = newGroupHead
        groupPrev = groupPrev.next

# 示例用法
# 创建链表: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
k = 2
new_head = reverseKGroup(head, k)
while new_head:
    print(new_head.val, end=" -> ")
    new_head = new_head.next
# 输出应为: 2 -> 1 -> 4 -> 3 -> 5 ->