25. K 个一组翻转链表

题目地址(25. K 个一组翻转链表)

https://leetcode.cn/problems/reverse-nodes-in-k-group/

题目描述

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

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

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

前置知识

公司

• 暂无

思路

关键点

• 像这种，同时设置四个指针就可以了
• prev前驱，first/second就是要倒转的首位节点，next后继

代码

• 语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 思路，还是使用四个指针：prev，first, second, next
        // 使用哑结点，简化操作
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        ListNode first = head;
        while (prev != null && first != null) {
            // 定位second和next
            ListNode second = prev;
            for (int i = 0; i < k; ++i) {
                second = second.next;
                if (second == null) {
                    return dummyHead.next;
                 }
            }
            ListNode next = second.next;

            // 翻转first -> second的链表
            reverse(first, second);
            prev.next = second;
            first.next = next;

            // 更新prev和next
            prev = first;
            first = next;
        }
        return dummyHead.next;
    }

    private void reverse(ListNode first, ListNode second) {
        ListNode node = first;
        ListNode prev = null;
        while (prev != second) {
            // 翻转
            ListNode next = node.next;
            node.next = prev;
            // 更新node和prev
            prev = node;
            node = next;
        }
    }
}

Go

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next:head}
    prev, first := dummy, head
    for prev != nil && first != nil {
        // step1.确定second和next
        second := prev;
        for i := 0; i < k; i++ {
            second = second.Next
            if second == nil {
                return dummy.Next
            }
        }
        next := second.Next

        // step2.倒转first到next
        reverse(first, second)
        prev.Next = second
        first.Next = next

        // step3.更新prev合first
        prev = first
        first = next
    }
    return dummy.Next
}


func reverse(first, second *ListNode){
    var prev *ListNode = nil
    node := first
    for prev != second {
        nex := node.Next
        node.Next = prev
        // 更新
        prev = node
        node = nex
    }

}

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：