leetcode_25. K 个一组翻转链表

One minute read
LeetCode
面试 • 算法 • 数据结构

K 个一组翻转链表

题目

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

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

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

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

开创一个新链表来存储反转后的思路行不通，因为规定时间复杂度是常数级的

尾插法

dummy    1     2     3     4     5
pre     head
tail    

# 用tail前进K个位置
dummy    1     2     3     4     5
pre     head       tail
		cur

# 尾插法：依次把cur移到tail后面
dummy    2     3    1     4     5
pre     cur  tail  head
        
# go on
dummy    3     2    1     4     5
pre     tail       head
		cur
....

解答

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    if k <= 1 || head == nil {
        return head
    }

    dummy := &ListNode{}
    dummy.Next = head
    pre, tail := dummy, dummy

    for {
        // 1. tail 前进k个位置
        var count int
        for count != k && tail != nil {
            tail = tail.Next
            count++
        }
        if tail == nil {    // 抵达尾部
            break
        }

        // 2. 尾插
        tmp := pre.Next // 暂存第一个
        for pre.Next != tail {
            cur := pre.Next
            pre.Next = cur.Next
            cur.Next = tail.Next
            tail.Next = cur
        }
        pre, tail = tmp, tmp
    }
    return dummy.Next
}

// 执行用时 :8 ms, 在所有 Go 提交中击败了15.08%的用户
// 内存消耗 :3.6 MB, 在所有 Go 提交中击败了100.00%的用户

其它解

  1. 临时栈，入栈出栈拼接
  2. 递归

优化

无


分享：