25. K 个一组翻转链表

最新推荐文章于 2025-03-05 19:57:32 发布

hodgeKou

最新推荐文章于 2025-03-05 19:57:32 发布

阅读量270

点赞数

分类专栏： LeetCode 文章标签：链表数据结构算法

本文链接：https://blog.csdn.net/csdn_kou/article/details/123058549

版权

LeetCode 专栏收录该内容

152 篇文章

订阅专栏

本文介绍如何用常数空间实现链表每k个节点翻转的算法，包括递归和反转部分链表的方法，并探讨了如何在不改变节点值的前提下进行实际节点交换。通过实例演示了如何处理链表长度非k整数倍的情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

25. K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
在这里插入图片描述

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

code


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	// 判断长度是否够 K，不够就直接返回了
    current := head
	for i := 0; i < k; i++ {
		if current == nil {
			return head
		}
		current = current.Next
	}
    pre := reverseList(head, current)

    // 递归，反转剩余的列表，原来的头结点反转后就变成了现在的尾节点，再把反转之后的剩余列表拼起来
	head.Next = reverseKGroup(current, k)
	// 返回新的头结点
    return pre
}

func reverseList(head *ListNode, current *ListNode) *ListNode {
    if head == current || head.Next == current {
        return head
    }

    temp := head
    node := reverseList(head.Next, current)
    temp.Next.Next = temp
    temp.Next = current

    return node
}