C++ 链表k个一组翻转

链表中的节点每k个一组翻转

http://www.nowcoder.com/questionTerminal/b49c3dc907814e9bbfa8437c251b028e

思路

由于题目要求空间复杂度,说明不可以递归,那么时间复杂度就只能是了,即遍历的同时一边分组一边翻转。

这样思路就清晰了,组内直接套链表翻转的模板,组间注意要保存上一组的tail(上一组翻转前的head)。考虑最后一组不满k的情况,这时只需要再翻转一次最后一组就可以了,总体时间复杂度就是。当然,求链表长度不反转最后一组也可行。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* last_tail;
    ListNode* reversek(ListNode* head, int k) {
        if(!head) return nullptr;
        ListNode* p = head;
        ListNode* prev = nullptr;
        int i;
        for(i = 0; i < k && p; ++i) {
            ListNode* tmp = p->next;
            p->next = prev;
            prev = p;
            p = tmp;
        }
        if(i < k) {
            return reversek(prev, i);
        }
        last_tail->next = prev;
        last_tail = head;
        return p;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        last_tail = new ListNode(0); // 哑节点,避免对链表头做单独处理
        ListNode* res = last_tail;

        ListNode* new_head = head;
        while(new_head) {
            new_head = reversek(new_head, k);
        }
        return res->next;
    }
};
全部评论

相关推荐

找到实习了&nbsp;给了150一天&nbsp;但是说是低代码&nbsp;值得去吗
码农索隆:是在没实习,可去,待个一两周,不行就润呗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务