现在位置: 首页 / 学习 / leetcode / 正文

LeetCode第二十五题：K 个一组翻转链表

  • admin
  • 学习
  • 2024-03-28
  • 56热度
  • 0评论

题目来源：LeetCode第二十五题

1.题目描述

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

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

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

示例 1：

LeetCode第二十五题：K 个一组翻转链表插图

输入：head = [1,2,3,4,5], k = 2

输出：[2,1,4,3,5]

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

2.解题思路

解法一：迭代法

  • 描述：遍历链表，确保剩余部分长度足够k个节点，如果不足k个节点则结束循环。找到每组的第一个和最后一个节点。这需要遍历当前组的k个节点。对每个分组进行翻转操作。翻转过程中，需要修改当前组内节点的指向。将翻转后的分组重新连接回原链表中。这包括将翻转组的头节点连接到前一组的尾部，以及将翻转组的尾部连接到下一组的头部（如果有）。
  • 时间复杂度：O(N)。
  • 空间复杂度：O(1)。
  • 参考代码：

java版：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 创建虚拟头节点方便处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 初始化指针
        ListNode prev = dummy;
        ListNode end = dummy;
        // 例如1->2->3->4->5，k=2
        // 移动end指针寻找第一组的末尾，end经过两次移动后指向2。
        // 检查end不为null，满足翻转条件。
        // 断开当前组与下一组的连接，即将end.next设置为null，这时链表分为了两部分：翻转部分1->2和未处理部分3->4->5。
        // 调用reverse翻转当前组，得到2->1，将prev.next指向翻转后的头节点2，同时将原先的头节点1的next指向下一组的起始节点3。
        // 更新prev为1，end也重新指向prev，准备下一轮遍历。
        while (end.next != null) {

            // 找到当前组的最后一个节点
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            // 如果end为null，说明剩余节点不足k个，不需要翻转
            if (end == null)
                break;
            // 记录下一组的起始节点
            ListNode nextGroupStart = end.next;
            // 断开当前组与下一组的连接
            end.next = null;
            // 记录当前组的起始节点
            ListNode start = prev.next;
            // 翻转当前组
            prev.next = reverse(start);
            // 翻转后start成了本组的末节点，连接到下一组的起始节点
            start.next = nextGroupStart;
            // 准备处理下一组，更新prev和end
            prev = start;
            end = prev;
        }

        return dummy.next;
    }

    // 翻转链表
    private ListNode reverse(ListNode head) {
        // 初始化一个指针prev为null，这将会是翻转后链表的尾部。
        ListNode prev = null;
        // 初始化一个指针curr，它会遍历原始链表，从头节点开始。
        // 例如1 -> 2 -> 3 -> null
        // 已翻转的：1 -> null 和 未翻转的：2 -> 3 -> null
        ListNode curr = head;
        while (curr != null) {
            // 临时存储curr的下一个节点，因为在翻转操作后，我们将失去对它的直接访问。
            ListNode nextTemp = curr.next;
            // 翻转curr节点的指向，将其next指针指向prev，实现翻转。
            curr.next = prev;
            // 将prev移动到curr，这步很关键，因为它确保了prev总是指向当前已翻转部分的头节点。
            prev = curr;
            // 将curr移动到nextTemp，即向前移动到下一个待翻转的节点。
            curr = nextTemp;
        }
        // 当循环结束时，prev将指向原链表的最后一个节点，即翻转后的新头节点。
        return prev;
    }
}

C++版：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || k == 1) return head;
        // 创建虚拟头节点方便处理
        ListNode dummy(0);
        dummy.next = head;
        // 初始化指针
        ListNode* prev = &dummy;
        ListNode* end = &dummy;
        // 例如1->2->3->4->5，k=2
       // 移动end指针寻找第一组的末尾，end经过两次移动后指向2。
       // 检查end不为null，满足翻转条件。
       // 断开当前组与下一组的连接，即将end.next设置为null，这时链表分为了两部分：翻转部分1->2和未处理部分3->4->5。
       // 调用reverse翻转当前组，得到2->1，将prev.next指向翻转后的头节点2，同时将原先的头节点1的next指向下一组的起始节点3。
       // 更新prev为1，end也重新指向prev，准备下一轮遍历。
        while (end->next != nullptr){
            // 找到当前组的最后一个节点
            for (int i = 0; i < k && end != nullptr; i++) end = end->next;
            // 如果end为null，说明剩余节点不足k个，不需要翻转
            if (end == nullptr) break;
            // 记录当前组的起始节点
            ListNode* start = prev->next;
            // 记录下一组的起始节点
            ListNode* nextGroupStart = end->next;
            // 断开当前组与下一组的连接
            end->next = nullptr;
            // 翻转当前组
            prev->next = reverse(start);
            // 翻转后start成了本组的末节点，连接到下一组的起始节点
            start->next = nextGroupStart;
            // 准备处理下一组，更新prev和end
            prev = start;
            end = prev;
        }
        return dummy.next;
    }

private:
    ListNode* reverse(ListNode* head) {
        // 初始化一个指针prev为null，这将会是翻转后链表的尾部。
        ListNode* prev = nullptr;
        // 初始化一个指针curr，它会遍历原始链表，从头节点开始。
        // 例如1 -> 2 -> 3 -> null
        // 已翻转的：1 -> null 和 未翻转的：2 -> 3 -> null
        ListNode* curr = head;

        while (curr != nullptr) {
            // 临时存储curr的下一个节点，因为在翻转操作后，我们将失去对它的直接访问。
            ListNode* nextTemp = curr->next;
            // 翻转curr节点的指向，将其next指针指向prev，实现翻转。
            curr->next = prev;
            // 将prev移动到curr，这步很关键，因为它确保了prev总是指向当前已翻转部分的头节点。
            prev = curr;
            // 将curr移动到nextTemp，即向前移动到下一个待翻转的节点。
            curr = nextTemp;
        }
        return prev;
    }
};

C版：

struct ListNode* reverse(struct ListNode* start, struct ListNode* end) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = start;
    while (curr != end) {
        struct ListNode* nextTemp = curr->next; // 暂存当前节点的下一个节点
        curr->next = prev; // 将当前节点指向前一个节点，实现翻转
        prev = curr; // 前一个节点前移
        curr = nextTemp; // 当前节点前移
    }
    return prev; // 返回翻转后的头节点，此时curr为end
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode dummy; // 创建一个哑节点，简化头节点的翻转处理
    dummy.next = head;
    struct ListNode* prev = &dummy;
    struct ListNode* end = head;

    while (end) {
        // 检查剩余部分长度是否足够k个节点
        for (int i = 0; i < k; i++) {
            if (!end) return dummy.next;
            end = end->next;
        }
        struct ListNode* start = prev->next; // 当前k组的起始节点
        struct ListNode* nextGroup = end; // 下一组的起始节点

        // 翻转当前k组，连接翻转后的链表
        prev->next = reverse(start, nextGroup);

        // 将翻转部分与下一部分连接
        start->next = nextGroup;

        // 为下一次翻转做准备
        prev = start;
    }
    return dummy.next;
}

解法二：递归法

  • 描述：遍历链表，检查从当前节点开始的剩余长度是否至少为k。如果不是，返回当前头节点，因为不需要翻转。如果当前段长度至少为k，则递归地调用函数处理剩下的链表部分。这一步将返回剩余部分翻转后链表的头节点。在确保当前段长度足够后，翻转当前的k个节点。这需要断开当前段和剩余链表的连接，独立翻转当前段，然后将翻转后的段连接到递归返回的链表头。将翻转后的当前段头节点连接到递归翻转的剩余链表上，形成新的链表。
  • 时间复杂度：O(n)。
  • 空间复杂度：O(n/k)。
  • 参考代码：

java版：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 首先检查链表中剩余节点是否少于k个
        ListNode curr = head;
        int count = 0;
        // 遍历链表计数，直到count等于k或遍历完链表
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }
        // 如果节点总数少于k，不进行翻转，直接返回当前头节点
        if (count < k) {
            return head;
        }
        // 当前有k个或以上的节点，可以进行翻转
        // 递归处理当前节点之后的部分
        ListNode prev = reverseKGroup(curr, k);
        // 递归返回的prev是翻转后链表的头节点，或是下一段需要处理的头节点
        while (count-- > 0) {
            // 临时保存当前节点的下一个节点
            ListNode temp = head.next;
            // 将当前节点指向prev，实现翻转
            head.next = prev;
            // 更新prev为当前节点，为下一次翻转做准备
            prev = head;
            // 移动head到下一个待翻转的节点
            head = temp;
        }
        // 返回翻转后的链表头节点
        return prev;
    }
}

C++版：

class Solution {
public:
    // 主函数：每k个节点翻转链表
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int count = 0;
        // 首先，找到第k个节点
        while (cur != nullptr && count < k) {
            cur = cur->next;
            count++;
        }

        // 如果节点总数小于k，则不进行翻转
        if (count < k) {
            return head;
        }

        // 翻转当前k个节点
        // 递归处理当前节点之后的部分
        ListNode* prev = reverseKGroup(cur, k);
        while (count-- > 0) {
            // 保存下一个节点
            ListNode* temp = head->next; 
            // 将当前节点指向prev，实现翻转
            head->next = prev;
            // 更新prev为当前节点，为下一次翻转做准备
            prev = head;
            // 移动head到下一个待翻转的节点
            head = temp; 
        }
        // 返回翻转后的链表头节点
        return prev;
    }
};

C版：

// 函数声明
struct ListNode* reverseKGroup(struct ListNode* head, int k);

// 辅助函数：翻转链表的一段，从head开始，翻转k个节点
struct ListNode* reverse(struct ListNode* head, int k) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (k > 0) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
        k--;
    }
    return prev;
}

// 主函数：递归地每k个节点一组翻转链表
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode* ptr = head;
    int count = 0;

    // 检查链表长度是否足够k个节点
    while (ptr != NULL && count < k) {
        ptr = ptr->next;
        count++;
    }
    
    // 如果链表长度足够，则进行翻转
    if (count == k) {
        // 递归处理链表的后续部分
        struct ListNode* reversedHead = reverseKGroup(ptr, k);
        
        // 翻转当前k个节点
        while (count > 0) {
            struct ListNode* temp = head->next; // 临时保存下一个节点
            head->next = reversedHead; // 将当前节点指向已翻转的头节点
            reversedHead = head; // 更新已翻转的头节点
            head = temp; // 移动到下一个节点
            count--;
        }
        head = reversedHead;
    }
    
    // 返回翻转后的链表头节点
    return head;
}

解法三：栈

  • 描述：创建一个栈用于暂存节点，以及一个虚拟头节点来简化链表头部的处理。遍历整个链表，每遍历到一个节点，就将它压入栈中。当栈中的节点数达到k时，开始逐一弹出栈中的节点，这个过程实际上是将这k个节点进行了翻转。翻转后的节点需要被正确连接到当前已处理链表的尾部，同时更新尾部指针指向最新处理的节点。如果链表的长度不是k的整数倍，最后剩余的不足k个节点应保持原有顺序，直接连接到当前链表的尾部。返回虚拟头节点的下一个节点，即翻转后链表的头节点。
  • 时间复杂度：O(N)。其中N是链表的长度。
  • 空间复杂度：O(k)。
  • 参考代码：

java版：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 使用栈来暂存节点，因为栈具有后进先出的特性，便于翻转节点
        Stack<ListNode> stack = new Stack<>();
        // 创建一个虚拟头节点，简化链表操作，尤其是头部翻转的处理
        ListNode dummy = new ListNode(0);
        // current用来遍历新链表，初始化为虚拟头节点
        ListNode current = dummy;
        // pointer用来遍历原链表，从头节点开始
        ListNode pointer = head;
        // 遍历原链表的每个节点
        while (pointer != null) {
            // 记录当前组的开始节点，用于判断是否满足k个节点
            ListNode groupStart = pointer;
            int count = 0;
            // 将k个节点压入栈中
            while (pointer != null && count < k) {
                stack.push(pointer);
                pointer = pointer.next;
                count++;
            }
            // 当栈满（即达到k个节点）时，依次弹出节点进行翻转操作
            if (count == k) {
                while (!stack.isEmpty()) {
                    current.next = stack.pop();
                    current = current.next;
                }
                // 栈中节点已经连接完毕，断开与后续节点的直接连接，以待下一步操作
                current.next = null;
            } else {
                // 不足k个节点，保持原顺序
                // 使用栈是为了逆序弹出，这里直接连接剩余节点
                current.next = groupStart;
                break; // 已经处理完所有节点，结束循环
            }
        }
        // 返回新链表的头节点
        return dummy.next;
    }
}

C++版：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        stack<ListNode*> stack; 
        // 虚拟头节点，简化头部翻转的操作
        ListNode dummy(0); 
        // current用于构建新链表，初始化指向虚拟头节点
        ListNode* current = &dummy; 
        // pointer用于遍历原链表
        ListNode* pointer = head; 

        while (pointer != nullptr) {
            // 记录当前组的开始节点
            ListNode* groupStart = pointer; 
            int count = 0;
            // 将k个节点压入栈中
            while (pointer != nullptr && count < k) {
                stack.push(pointer);
                pointer = pointer->next;
                count++;
            }
            // 如果栈中的节点数达到k，依次弹出并连接到新链表上
            if (count == k) {
                while (!stack.empty()) {
                    // 连接翻转后的节点
                    current->next = stack.top(); 
                    // 弹出栈顶元素
                    stack.pop(); 
                    // 更新current指针
                    current = current->next; 
                }
                // 断开与后续节点的直接连接
                current->next = nullptr; 
            }
            else {
                // 如果节点数不足k个，保持原顺序
                // 直接连接剩余的节点，不需再次使用栈
                current->next = groupStart;
                break; 
            }
        }
        // 返回新链表的头节点
        return dummy.next; 
    }
};

C版：

// 定义栈结构体
struct Stack {
    struct ListNode** items; // 存储链表节点指针的动态数组
    int top; // 栈顶位置索引，初始为-1表示空栈
    int capacity; // 栈的容量
};

// 创建栈，参数为栈的容量
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1; // 初始化栈为空
    stack->items = (struct ListNode**)malloc(sizeof(struct ListNode*) * capacity);
    return stack;
}

// 检查栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

// 检查栈是否已满
int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 向栈中压入一个元素
void push(struct Stack* stack, struct ListNode* item) {
    if (isFull(stack)) {
        return; // 如果栈已满，则不进行操作
    }
    stack->items[++stack->top] = item; // 将节点指针压入栈中
}

// 从栈中弹出一个元素
struct ListNode* pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return NULL; // 如果栈为空，则返回NULL
    }
    return stack->items[stack->top--]; // 返回栈顶元素并更新栈顶索引
}

// 每k个节点一组翻转链表的函数
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct Stack* stack = createStack(k); // 创建一个栈，容量为k
    struct ListNode dummy; // 虚拟头节点，简化头部处理
    dummy.next = NULL;
    struct ListNode* current = &dummy; // current用于构建翻转后的链表
    struct ListNode* pointer = head; // pointer用于遍历原链表

    while (pointer != NULL) {
        int count = 0;
        // 将k个节点压入栈中
        while (pointer != NULL && count < k) {
            push(stack, pointer);
            pointer = pointer->next;
            count++;
        }
        // 如果栈满，说明达到了k个节点，进行翻转
        if (count == k) {
            while (!isEmpty(stack)) {
                current->next = pop(stack); // 弹出栈中节点并连接到current后
                current = current->next; // 移动current到新加入的节点
            }
            current->next = NULL; // 断开与后续节点的直接连接，防止成环
        }
        else {
            // 不足k个节点时，栈中的节点顺序与原链表顺序相反，需要逆序弹出以恢复原顺序
            struct ListNode** tempStack = (struct ListNode**)malloc(count * sizeof(struct ListNode*)); // 动态分配临时数组
            int tempCount = 0; // 临时计数器
            while (!isEmpty(stack)) {
                // 将栈中元素逆序存入临时数组
                tempStack[tempCount++] = pop(stack);
            }
            // 逆序将节点从临时数组中取出，恢复原链表顺序
            for (int i = tempCount - 1; i >= 0; i--) {
                current->next = tempStack[i];
                current = current->next;
            }
            current->next = pointer; // 直接连接剩余节点
            free(tempStack); // 释放临时数组所占用的内存
            break; // 结束循环
        }
        
    }

    free(stack->items); // 释放栈使用的动态数组内存
    free(stack); // 释放栈结构体占用的内存

    return dummy.next; // 返回翻转后链表的头节点，即虚拟头节点的下一个节点
}