首页 > 代码库 > LeetCode --- 25. Reverse Nodes in k-Group

LeetCode --- 25. Reverse Nodes in k-Group

2024-11-24 23:35:39   203人阅读

题目链接：Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

这道题的要求是每次以k个节点为单位翻转链表，如果最后不足k个，这不翻转。要求：使用恒定空间，不允许修改链表中的数值，仅可以改变链表节点本身。

这道题考察的是链表处理，算是Swap Nodes in Pairs的扩展吧。同样还是现在链表前面加个头，便于统一处理链表的所有节点。

思路就是领p和q都指向要翻转的第一个节点的前一节点，然后逐步把q往后移k位，这样q就指向要翻转的最后一个节点，接下来逐个把p和q之间的节点插入到q的后面即可。

假设k=3，加头之后链表为：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL。

领p指向要翻转节点的第一个节点的前一节点，q指向要翻转节点的最后一个节点，即：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
     ^              ^
     |              |
     p              q

接下来，翻转(p, q]之间的节点，只需要逐个把p后面的节点插入到q的后面即可。

在逐步插入节点前，需要一点准备工作：首先需要将p的next的节点（即翻转后的最后节点）用tempp记录一下，然后使p的next指向q指向的节点，这样就把要翻转的最后节点连接到了最前面，p移动到翻转后的最后节点（即temp指向的节点），便于下一次翻转。结果如下：
     |------------->|
h -> 0    1 -> 2 -> 3 -> 4 -> 5 -> NULL
          ^         ^
          |         |
       p、tempp     q

正式翻转的时候，就是把tempp和q之间的节点逐个以头插入的方式插入到q后面，因此循环判停条件为tempp!=q。首先需要临时变量temp记录tempp的next指向的节点，然后令tempp的next指向q的next指向的节点，令q的next指向tempp指向的节点（就是把tempp的next的节点逐个放到q后面），最后tempp再右移，即tempp指向之前记录temp的next的temp指向的节点：
h -> 0 -> 3 -> 2 -> 1 -> 4 -> 5 -> NULL
                    ^
                    |
                    p

进而继续下一轮翻转，以此类推，不断循环。。。

时间复杂度：O(n)

空间复杂度：O(1)

 1 class Solution
 2 {
 3 public:
 4     ListNode *reverseKGroup(ListNode *head, int k)
 5     {
 6         ListNode *h = new ListNode(0), *p = h;
 7         h -> next = head;
 8 
 9         while(p -> next != NULL)
10         {
11             ListNode *q = p;
12             for(int i = 0; i < k && q != NULL; ++ i)
13                 q = q -> next;
14 
15             if(q == NULL)
16                 break;
17 
18             ListNode *tempp = p -> next;
19             p -> next = q;
20             p = tempp;
21             while(tempp != q)
22             {
23                 ListNode *temp = tempp -> next;
24                 tempp -> next = q -> next;
25                 q -> next = tempp;
26                 tempp = temp;
27             }
28         }
29 
30         return h -> next;
31     }
32 };

转载请说明出处：LeetCode --- 25. Reverse Nodes in k-Group

LeetCode --- 25. Reverse Nodes in k-Group


联系
我们