力扣25. K 个一组翻转链表

Problem: 25. K 个一组翻转链表

题目描述

思路

1.创建虚拟头节点dummy并将其next指针指向head，创建指针pre、end均指向dummy；
2.编写反转单链表的函数reverse
3.当end -> next 不为空时：

3.1.每次k个一组将end指针后移；
3.2.判断当end指针为空时直接退出循环；
3.3.创建nextP指针指向end -> next,strat指针指向pre -> next;end的next指针置空；
3.4.从start指向的节点开始反转链表，并使得pre的next指针指向其；
3.5.start的next指针指向nextP，使得原始链表能连接起来
3.6.使pre指针指向start指针，end指针指向pre指针

复杂度

时间复杂度:

$O(n)$；其中$n$为链表的长度

空间复杂度:

$O(n)$

Code

/**
 * 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:
    /**
     * A set of K reversed single-linked lists
     * 
     * @param head The head node of the list to be reversed
     * @param k Number of nodes to be reversed
     * @return ListNode*
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        //Create a virtual node 
        ListNode* dummy = new ListNode(INT_MIN);
        ListNode* pre = dummy;
        ListNode* end = dummy;
        dummy -> next = head;
        while (end -> next != nullptr) {
            //Each k is in a group
            for (int i = 0; i < k && end != nullptr; ++i) {
                //Pointer end moves back
                end = end -> next;
            }
            if (end == nullptr) {
                break;
            }
            ListNode* start = pre -> next;
            ListNode* nextP = end -> next;
            //disconnect
            end -> next = nullptr;
            //reverse k nodes and return the new headnode which 
            //is the last node of k nodes
            pre -> next = reverse(start);
            //connect next group k nodes by next pointer
            start -> next = nextP;
            pre = start;
            end = pre;
        }
        return dummy -> next;
    }

    /**
     * Reverse the single linked list
     * 
     * @param head The node of the list to be reversed
     * @return ListNode*
     */
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nextP = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nextP;
        }
        return pre;
    }
};