链表中的节点每k个一组翻转

1. 题目描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。 要求空间复杂度 O(1)

2. 思路

1. 数组暂存组
   • 遍历链表
     • 按照n个分组
   • 对于每个组，进行反转
   • 遍历组，构造链表
   • 该实现会新建节点并使用 O(N) 额外空间，不满足题目的 O(1) 额外空间和“只能更改节点本身”的约束，仅保留为历史实现
2. 遍历同时翻转
3. 

3. 实现

3.1. 数组暂存组

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k <= 1 {
        return head
    }

    var groups [][]int
    var group []int
    current := head
    i := 0
    for {
        if current == nil {
            if len(group) > 0 {
                groups = append(groups, group)
                group = make([]int, 0) 
            }
            break
        }

        group = append(group, current.Val)
        i++
        if i % k == 0 {
            groups = append(groups, group)
            group = make([]int, 0)
        }
        current = current.Next
    }

    for _, group := range groups {
        if len(group) == k {
            reverse(group)
        }
    }

    dummyHead := &ListNode{}
    current = dummyHead
    for _, group := range groups {
        for _, val := range group {
            current.Next = &ListNode{Val:val}
            current = current.Next
        }
    }
    return dummyHead.Next
}

func reverse(group []int) {
    i := 0
    j := len(group)-1
    for i < j {
        group[i],group[j] = group[j], group[i]
        i++
        j--
    }
}

3.2. 遍历同时翻转

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type KNodeGroup struct {
    head *ListNode
    tail *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummyHead := &ListNode{}
    d := dummyHead
    current := head
    for {
        kGroup,ok := findKGroupHead(current, k)
        if ok {
            current = kGroup.tail.Next
            d.Next = reverseList(kGroup.head, k)
            d = kGroup.head
        }else {
            d.Next = current
            break
        }
       
    }
    return dummyHead.Next
}

func findKGroupHead(head *ListNode, k int)(*KNodeGroup,bool) {
    count := 0
    current := head
    for current != nil {
        count++
        if count == k {
            return &KNodeGroup{head:head, tail:current}, true
        }
        current = current.Next
    }
    return nil, false
}

func reverseList(head *ListNode, k int)*ListNode {
    var pre *ListNode
	current := head
	var next *ListNode
	for i := 0; i < k; i++ {
		next = current.Next
		current.Next = pre
		pre = current
		current = next
	}
 
	return pre
}

3.3. 其他

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
//{1,2,3,4,5},2
func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 1 {
		return head
	}

	res := &ListNode{}
	res.Next = head

	pre := res
	cur := head
	var tmp *ListNode
	length := 0
	for head != nil {
		length++
		head = head.Next
	}


	for i := 0; i < length/k; i++ {
		for j := 1; j < k; j++ {
			tmp = cur.Next
			cur.Next = tmp.Next
			tmp.Next = pre.Next
			pre.Next = tmp
		}

		pre = cur
		cur = cur.Next
	}

	return res.Next
}

4. 参考

• 链表中的节点每k个一组翻转_牛客题霸_牛客网
• 25. K 个一组翻转链表 - 力扣（LeetCode）