K个节点翻转链表

概述

起因:leetcode题目 25. K 个一组翻转链表

问题描述

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

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

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例一:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

解决方法

我们需要构建一个函数,它会对链表进行K个节点翻转。而不断使用这个函数,就可以对每K个节点进行翻转。

点击查看代码
    struct Res{
        ListNode *head;
        bool flag;
        ListNode *tail;
    };

    Res reverse(ListNode* head,int k){
        ListNode newHead;
        ListNode *subHead,*subTail,*cur,*temp;
        //subHead 记录反转过程的头节点
        //subTail 记录反转过程的尾节点
        //cur 要反转的节点
        //temp 用于反转的中间变量

        int cnt = 0; //记录长度

        if(head){
            subHead = head;
            subTail = head;
            cur = head->next;
            cnt++;
        }

        while(cur && cnt<k){
            temp = cur;
            cur = cur->next;

            subTail->next = temp->next;
            temp->next = subHead;

            subHead = temp;
            cnt++;
        }
        bool flag = true;
        if(cnt<k) flag = false;
        return {subHead,flag,subTail};
    }

函数逻辑

  • 一开始翻转链表的headtail都是正常链表的头节点,cur则是要进行翻转的节点

    • 我们把cur作为新的head,即旧的head会成为cur的下一个节点。
    • cnt 进行自增加一
  • 重复这个过程,直到cur为空。

  • 然后判断 cntK 的关系:cnt < K 的话,则未能反转 K 个节点。flagFalse

注意:这个过程中tail不需要变化,因为一开始的正常链表头节点就是翻转后的尾节点。

其中,函数返回翻转后的头节点和尾节点。特别地,flag是判断是否翻转了K个数。

实现不满足K个节点则不翻转

当不满足K个节点时,函数返回的 res 中的flag属性会为False
这时对这个翻转后的链表再次进行翻转的话,就可以实现不翻转。

主函数实现

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *newHead,*subTail;
    
    //首先进行一次翻转,并初始newHead和subTail
    
    auto res = reverse(head,k);
    newHead = res.head;     
    subTail = res.tail;
    
    //如果第一次翻转就不满足K个节点,再次进行翻转,并返回新的newHead
    if(res.flag == false){
        res = reverse(newHead,k);
        newHead = res.head;
        subTail = res.tail;
        return newHead;
    }          
  
    //对每K个节点进行翻转
    while(1){
        auto res = reverse(subTail->next,k);        
      
        //不满足K个节点,再次翻转,并直接返回结果。
        if(res.flag == false){
            res = reverse(res.head,k);
            return newHead;
        }
        
        // 对subTail进行更新:链接翻转后的子链表,并把subTail更新为子链表的tail。
        subTail->next = res.head;
        subTail = res.tail;
        cout<<subTail->val<<endl;
    }

    return newHead;
}