signed

QiShunwang

“诚信为本、客户至上”

Leetcode 25. K 个一组翻转链表

2021/3/21 10:11:30   来源:

Leetcode 25. K 个一组翻转链表

(个人复习用)
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

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

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

进阶:

你可以设计一个只使用常数额外空间的算法来解决此问题吗?
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
在这里插入图片描述在这里插入图片描述在这里插入图片描述
一.先计算链表长度,模拟迭代
在头结点前加入虚拟头结点方便操作
虚拟头结点(用dummy命名)
在这里插入图片描述
在这里插入图片描述

c++
/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        int count = 0;
        while(head) {
            head = head->next;
            count++;
        }
        head = dummy->next;
        ListNode* pre = dummy;
        ListNode* cur = head;
        ListNode* nex;
        for(int i = 0; i < count/k; i++) {
            for(int j = 0; j < k-1; j++) {
                nex = cur->next;
                cur->next = nex->next;
                nex->next = pre->next;
                pre->next = nex;
            }
            pre = cur;
            cur = pre->next;
        }
        return dummy->next;
    }
};

二.递归(抄的)

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head || !head->next || k == 1) return head;
        ListNode* seg = head;
        int x = k;
        while(x > 0)
        {
            seg = seg->next;
            --x;
            if(!seg&&x>0) return head; //如果最后后面没有k nodes就不要reverse了
        }
        //开始转换,结束时prev会变成头,所以返回prev
        ListNode* prev = head;
        ListNode* now = head->next;
        while(now && now!=seg)
        {
            ListNode* temp = now->next;
            now->next = prev;
            prev = now;
            now = temp;
        }
        head->next = reverseKGroup(seg, k);
        return prev;
    }
};

作者:Xiaohu9527
链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/gan-jue-huan-xing-bi-bie-ren-de-hao-dong-bxxp/