24. Swap Nodes in Pairs + 25. Reverse Nodes in k-Group

▶ 问题：单链表中的元素进行交换或轮换。

▶ 24. 每两个元素进行翻转。如 [1 → 2 → 3 → 4 → 5] 变换为 [2 → 1 → 4 → 3 → 5]

● 初版代码，4 ms

 1 class Solution
 2 {
 3 public:
 4     ListNode* swapPairs(ListNode* head)
 5     {
 6         int length;
 7         ListNode newHead(-999), *x, *y;
 8         newHead.next = head;                                            // 添加头结点，方便操作原链表的首元
 9         for (x = head, length = 0; x != nullptr; x = x->next, length++);// 计算链表元素个数
10         if (length <= 1)                                                // 无需交换的情形
11             return head;
12         for (x = &newHead, y = x->next; y != nullptr && y->next != nullptr; x = x->next->next, y = y->next)
13         {                                                               // y 指向需要交换的两个节点的靠前一个，x 指向 y 的再前一个节点
14             x->next = x->next->next;                                    
15             y->next = x->next->next;                                    
16             x->next->next = y;                                          
17         }
18         return newHead.next;
19     }
20 };

● 改良版代码，3 ms 。减少了结点计数，改变了操作顺序，后面 k 元轮换的算法与此类似。

 1 class Solution
 2 {
 3 public:
 4     ListNode* swapPairs(ListNode* head)
 5     {
 6         if (head == nullptr || head->next == nullptr)// 0 或 1 个元素
 7             return head;
 8         ListNode newHead(-999);
 9         newHead.next = head;
10         for (ListNode *x = &newHead, *y = x->next->next;;)// y指向需要交换的两个元素的后者
11         {
12             x->next->next = x->next->next->next;
13             y->next = x->next;
14             x->next = y;
15             x = y->next;                                  // 一定存在，不用检查 nullptr
16             if (x->next == nullptr || (y = x->next->next) == nullptr)
17                 break;
18         }
19         return newHead.next;
20     }
21 };

▶ 25. 每 k 个元素进行翻转。如 k = 4 时，[1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9] 变换为 [4 → 3 → 2 → 1 → 8→ 7 → 6 → 5 → 9]

● 自己的代码，26 ms

 1 class Solution
 2 {
 3 public:
 4     ListNode* reverseKGroup(ListNode* head, int k)
 5     {
 6         int length, front;
 7         ListNode newHead(-999), *x, *y, *z, *w;
 8         for (x = head, length = 0; x != nullptr; x = x->next, length++);// 求链表长，是否还剩 k 元可以进行轮换由 length 决定
 9         if (length < 2 || k < 2 || length < k)                          // 不需要调整的情形
10             return head;
11         for (front = 0, newHead.next = head, x = &newHead; (length - front) / k;)// front 代表当前处理的元素的最大序号（w 指向的元素的编号）
12         {
13             y = x, z = y->next, w = z->next;
14             for (front++; front % k; front++)// 每次循环先跳转 y、z、w 建立一个链接
15             {
16                 y = z, z = w, w = w->next;
17                 z->next = y;
18             }
19             x->next->next = w;               // 之后建立与 x 有关的链接
20             y = x->next;
21             x->next = z;
22             x = y;
23         }
24         return newHead.next;
25     }
26 };

● 大佬的代码，25 ms

 1 class Solution
 2 {
 3 public:
 4     ListNode* reverseKGroup(ListNode* head, int k)
 5     {
 6         ListNode *node = head, *rev;
 7         for (int i = 0; i < k; node = node->next, i++)
 8         {
 9             if (node == NULL)
10                 return head;
11         }
12         rev = reverse(head, node);
13         head->next = reverseKGroup(node, k);
14         return rev;
15     }
16     ListNode * reverse(ListNode *start, ListNode *end)
17     {
18         ListNode *prev = end, *next;
19         while (start != end)
20         {
21             next = start->next;
22             start->next = prev;
23             prev = start;
24             start = next;
25         }
26         return prev;
27     }
28 };