140-k个一组反转单链表(非递归)

心已赠人 2023-01-08 09:28 147阅读 0赞

**题目：**  
给定的链表是1->2->3->4->5

对于 k=2, 你应该返回 2→1→4→3→5

对于 k=3, 你应该返回 3→2→1→4→5

**方法：**  
1、增加一个新的头节点，先计算链表长度len，那么通过len/k次反转可以达到目的  
2、在每次反转过程中，p指针指向前一个节点，q来保存当前cur节点的下一个节点  
3、将cur断链，拆除以后用**头插法**插入p的后面

ListNode *reverseKGroup(ListNode *head, int k)
    {
        
        if (k < 2 || head == NULL || head->next == NULL)
        {
        
            return head;
        }
        
        ListNode *newHead = new ListNode(0);//申请新的头结点并初始化为0 
        newHead->next = head;//新的头结点与传入链表的头结点相连接 
        ListNode *cur = head;//当前结点 
        int len = 0;
        while (cur != NULL)//计算链表的长度 
        {
        
            len++;
            cur = cur->nxt;
        }
        cur = head;//从头开始记录 
        ListNode *p= newHeade;
        ListNode *q= NULL;
        for (int i = 0; i < len / k; ++i)//反转几次 
        {
        
            for (int j = 1; j < k; ++j)//每次反转需要进行的次数 
            {
        
                q=cur->next;//保存当前cur节点的下一个结点。
                cur->next=q->next;
                q->next=p->next;
                p->next=q;
            }
            p = cur;//标记往后走之前的cur结点 
            cur = cur->next;//cur往后走 
        }
        return newHead->next;//返回新链表的头结点 
    }

运行图解如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/eebd6f78e97746eeaabf5ad6bdb06832.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/a45fc703ecda4c949eb36d9d4ea2cab4.png