leetcode25：K个一组翻转链表

题目链接

leetcode

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现

    子问题（后面这部分链表）和原问题（整条链表）的结构完全相同，这就是递归性质。
    算法流程如下：
        1.反转以 head 开头的 k 个元素。
        2.将第 k + 1 个元素作为 head，递归调用 reverseKGroup 函数。
        3.将上述两个过程的结果连接起来。
    
    时间复杂度：O(n)
        设链表长度为 N，将链表分成 N/k 个长度为 k 的子链表。
        每个子链表的翻转操作需要 O(k) 的时间，因此总的时间复杂度是 O(N)。
    空间复杂度：O(n)
        递归调用会使用到栈空间，其空间复杂度取决于链表的长度，即 O(N)。
        此外，没有使用额外的空间（除了输出结果外），所以总的空间复杂度也是 O(N)。
*/
class Solution_0 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || k == 0) {
            return head;
        }

        // 找到这一组 k 个节点的首尾节点
        ListNode *start, *end;
        start = end = head;
        for (int i = 0; i < k; i++) {
            if (end == nullptr) {
                return head;
            }
            end = end->next;
        }

        // 反转这一组的节点 [start, end)
        ListNode *prev, *cur;
        prev = nullptr, cur = start;
        while (cur != end) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        // 递归调用，反转后面的链表并连接
        start->next = reverseKGroup(end, k);
        return prev;
    }
};

/*
    迭代实现
    思路参考：24.Swap Nodes in Pairs
    
    时间复杂度：O(n)
        设链表长度为 N，将链表分成 N/k 个长度为 k 的子链表。
        每个子链表的翻转操作需要 O(k) 的时间，因此总的时间复杂度是 O(N)。
    空间复杂度：O(n)
        递归调用会使用到栈空间，其空间复杂度取决于链表的长度，即 O(N)。
        此外，没有使用额外的空间（除了输出结果外），所以总的空间复杂度也是 O(N)。
*/
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* prevEnd = dummy;

        while (prevEnd != nullptr) {
            // 找到这一组 k 个节点的首尾节点
            ListNode *start = prevEnd->next, *end = prevEnd;
            for (int i = 0; i < k && end != nullptr; i++) {
                end = end->next;
            }
            if (end == nullptr) {
                break;
            }

            // 反转这一组节点 [start, end]
            ListNode* nextStart = end->next;
            ListNode *prev = nullptr, *cur = start;
            while (cur != nextStart) {
                ListNode* temp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = temp;
            }

            // 连接反转后的子链表
            start->next = nextStart;
            prevEnd->next = end;
            prevEnd = start;
        }

        return dummy->next;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5};
    int k = 2;

    // 创建链表
    ListNode* head = createList(nums);

    // 翻转操作
    ListNode* result = solution.reverseKGroup(head, k);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    deleteList(result);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*  
    递归实现

    子问题（后面这部分链表）和原问题（整条链表）的结构完全相同，这就是所谓的递归性质。
    根据递归性质，算法流程如下：
        1. 先反转以 head 开头的 k 个元素。
        2. 将第 k + 1 个元素作为 head，递归调用 reverseKGroup 函数。
        3. 将上述两个过程的结果连接起来。
        
    时间复杂度：O(n)
        对链表进行一次遍历，对于每个节点的操作都是常数级的。
    空间复杂度：O(1)
        几个固定的指针变量。
*/
func reverseKGroup_0(head *ListNode, k int) *ListNode {
    if head == nil || k == 0 {
        return head
    }

    // 找到这一组 k 个节点 [start, end)
    start, end := head, head
    for i := 0; i < k; i++ {
        if end == nil {
            return head
        }
        end = end.Next
    }

    // 反转这一组的节点 [start, end)
    var prev *ListNode
    cur := start
    for cur != end {
        temp := cur.Next
        cur.Next = prev
        prev = cur
        cur = temp
    }

    // 递归调用，移动到这一组的最后一个节点
    head.Next = reverseKGroup(end, k)
    return prev
}

/*
    迭代实现

    定义一个反转链表的辅助函数，
    每次找到每 k 个节点的头和尾，将这一段链表反转，
    再连接到之前的链表上。
    
    时间复杂度：O(n)
        对链表进行一次遍历，对于每个节点的操作都是常数级的。
    空间复杂度：O(1)
        几个固定的指针变量。
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{-1, head}
    prevEnd := dummy

    for {
        // 找到这一组 k 个节点的首尾节点
        start, end := prevEnd.Next, prevEnd
        for i := 0; i < k && end != nil; i++ {
            end = end.Next
        }
        if end == nil {
            break
        }

        nextStart := end.Next
        // 反转链表 [start, nextStart)
        var prev *ListNode
        cur := start
        for cur != nextStart {
            temp := cur.Next
            cur.Next = prev
            prev = cur
            cur = temp
        }

        // 反转后的子链表连接到原链表
        start.Next = nextStart
        prevEnd.Next = end
        prevEnd = start
    }

    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        head    []int
        k       int
        expected []int
    }{
        {
            head:     []int{1,2,3,4,5},
            k:        2,
            expected: []int{2,1,4,3,5},
        },
        {
            head:     []int{1,2,3,4,5},
            k:        3,
            expected: []int{3,2,1,4,5},
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.head)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
        result := reverseKGroup(head, tc.k)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}