美文网首页leetcode
25. k个一组翻转链表

25. k个一组翻转链表

作者: geaus | 来源:发表于2020-05-16 16:46 被阅读0次

    题目描述

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
    k 是一个正整数,它的值小于或等于链表的长度。
    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    示例:

    给你这个链表:1->2->3->4->5
    当 k = 2 时,应当返回: 2->1->4->3->5
    当 k = 3 时,应当返回: 3->2->1->4->5
    

    说明:
    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

    解题思路

    找到每组链表节点的头和尾(head、tail),将这一组节点翻转;
    另外,需要保留每组节点的上一个节点(prev、next),方便接上翻转后的头、尾节点;
    对于第一组节点,由于没有prev,需要设定一个虚的prev节点(hair),另外这样也方便直接返回结果(hair->next)。

    pair<ListNode*, ListNode*> helper(ListNode* head, ListNode* tail){
        ListNode* prev = tail->next;
        ListNode* curr = head;
    
        while(prev!=tail){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
    
        return pair<ListNode*, ListNode*>(tail, head);
    }
    
    ListNode* reverseKGroup(ListNode* head, int k){
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* prev = hair;
        
        while(head){
            ListNode* tail = prev;
            for(int i=0; i<k; i++){
                tail = tail->next;
                if(!tail)
                    return hair->next;
            }
    
            ListNode* nex = tail->next;
            tie(head, tail) = helper(head, tail);
    
            prev->next = head;
            tail->next = nex;
            prev = tail;
            head = nex;
        }
        
        return hair->next;
    }
    

    相关文章

      网友评论

        本文标题:25. k个一组翻转链表

        本文链接:https://www.haomeiwen.com/subject/jmkrohtx.html