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

• 思路
• 解题方法
• 复杂度
• Code

思路

官方思路

多指针+翻转链表+结构体

解题方法

定义多指针
用来查找的头节点
每一组的头节点
每一组的尾节点,用来找到下一组头节点

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(1)$

Code

/* 定义保存两个地址的结构体
 * 用来保存反转后结果的头节点和尾节点
 */
typedef struct {
    struct ListNode* head; 
    struct ListNode* tail; 
} TwoAddress;
// 反转中间链表
TwoAddress* reverse(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    TwoAddress* ans = (TwoAddress*)malloc(sizeof(TwoAddress));
    ans->tail = head;
    while(curr){
        struct ListNode* temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    ans->head = prev;
    return ans;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    // 每一组的查找头节点,做标志用,本身不查找,并且用来连接两组之间的头节点和尾节点
    struct ListNode* prev = dummyHead; 
    // 翻转头节点
    struct ListNode* curr = head;
    while(curr){
        // 尾节点,查找本组的末尾,将其next设置为NULL
        struct ListNode* tail = prev;
        for(int i=0;i<k;i++){
            tail = tail->next;
            if(!tail) return dummyHead->next;
        }
        // 保存下一组的头节点
        struct ListNode* next = tail->next;
        tail->next = NULL;  //断开
        TwoAddress* temp = reverse(curr);  // 翻转这组
        prev->next = temp->head;  // 拼接
        temp->tail->next = next;
        prev = temp->tail;
        curr = temp->tail->next;
    }
    return dummyHead->next;
}