K 个一组翻转链表

力扣 25. K 个一组翻转链表

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

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

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

方案一：遍历链表，按照 k 个节点反转链表，然后处理反转后相邻链表的关系。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    // 定义哨兵节点
    // 使得每组链表都可以有相邻节点（主要是头节点）
    dummy := &ListNode{
        Next: head,
    }
    pre := dummy
    // 遍历链表
    for head != nil {
        // 获取当前组链表的尾节点
        // 即需要反转的部分为 head-end 间的节点
        end := getNode(head, k)
        // 如果下一组节点不足 k 个，则终止循环
        // 下一组节点不足 k 个则 end 为 nil
        if end == nil {
            break
        }

        // 计算下一个组节点的头节点
        nextGroupHead := end.Next
        
        // 反转链表
        // 反转从 head 到 nextGroupHead 前一个节点之间的链表部分
        // nextGroupHead 用来当作终止反转的标志
        reverseList(head, nextGroupHead)
        
        // 处理反转后的链表同上一组链表的之间的链接关系
        pre.Next = end
        head.Next = nextGroupHead
        pre = head

        // 更新头节点
        head = nextGroupHead
    }
    return dummy.Next
}

// getNode 获取当前链接节点之后的第 k 个节点。
// 不够 k 个 返回 nil。
func getNode(head *ListNode, k int) *ListNode {
    for head != nil {
        if k--; k == 0 {
            return head
        }
        head = head.Next
    }
    return nil
}

// reverseList 反转从 head 到 stop 前一个节点部分的链表。
func reverseList(head, stop *ListNode) {
    pre := head
    head = head.Next
    for head != stop {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }  
}

时间复杂度：O(n)，因为需要遍历链表中所有元素才能实现反转，且中途查找每组节点组的末尾节点，反转节点组这些操作进行的遍历都是 k 次左右，所以总体时间复杂度为 O(k*n)。
空间复杂度：O(1)，因为使用了常数量个变量用作辅助计算，所以空间复杂度为 O(1)。

K 个一组翻转链表

力扣 25. K 个一组翻转链表

CATALOG

FEATURED TAGS