25. K 个一组翻转链表

Link

力扣

Problem

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

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

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

示例 1：

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

示例2：

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

提示：

• 链表中的节点数目为 n

• 1 <= k <= n <= 5000

• 0 <= Node.val <= 1000

Solution

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{-1, head}
    cur, pre := dummy, dummy

    cnt := 0
    for cur.Next != nil {
        cur = cur.Next
        cnt++
        if cnt%k == 0 {
            next := cur.Next
            cur.Next = nil
            nh, nt := reverse(pre.Next)
            
            pre.Next = nh
            nt.Next = next

            pre, cur = nt, nt
        }
    } 

    return dummy.Next
}

func reverse(head *ListNode) (*ListNode, *ListNode){
    cur := head
    var pre, next *ListNode

    for cur != nil {
        next = cur.Next
        cur.Next = pre
        pre = cur 
        cur = next
    }
    return pre, head
}

C++