LeetCode K个一组翻转链表

小灰灰 2023-06-04 14:53 17阅读 0赞

题目链接：[https://leetcode-cn.com/problems/reverse-nodes-in-k-group/][https_leetcode-cn.com_problems_reverse-nodes-in-k-group]

### 题目大意 ###

略。

### 分析 ###

逆转每一段，然后和上一段与下一段衔接即可，加头结点会比较方便。

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode* reverseKGroup(ListNode* head, int k) {
    12         if(head == NULL || k == 1) return head;
    13         
    14         int len = getLen(head);
    15         ListNode *start = head, *lastTail = new ListNode(0), *newhead = lastTail;
    16         newhead->next = head;
    17         
    18         for(int i = 0; i < len / k; ++i) {
    19             lastTail->next = reverseGroup(start, k); // 和上一段尾巴接上
    20             lastTail = start;
    21             start = lastTail->next;
    22         }
    23         
    24         return newhead->next;
    25     }
    26     
    27     // 返回反转链表的头结点,顺便把尾部接到下一段头部
    28     ListNode* reverseGroup(ListNode* head, int k) {
    29         ListNode *p1 = head, *p2 = head->next;
    30         
    31         for(int i = 0; i < k - 1; ++i) {
    32             head->next = p2->next;
    33             p2->next = p1;
    34             p1 = p2;
    35             p2 = head->next;
    36         }
    37         
    38         return p1;
    39     }
    40     
    41     int getLen(ListNode *head, ListNode *end = NULL) {
    42         int ret = 0;
    43         while(head != end) {
    44             ++ret;
    45             head = head->next;
    46         }
    47         return ret;
    48     }
    49 };

转载于:https://www.cnblogs.com/zaq19970105/p/11351028.html

[https_leetcode-cn.com_problems_reverse-nodes-in-k-group]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/57e9f180b48a413faf2c03b0b6bf2c3f.png