algorithm - 反转和合并链表

Question

问题：给定一个排序的链表

1->2->3->4->5->6->7

更改链表中的指针以使其

7->1->6->2->5->3->4

使用常数空间。

我尝试使用以下算法解决它：

1. 使用 2 个节点，一个快速节点和一个慢速节点找到链表的中间节点。

2. 从中间节点反转链表。将中间节点标记为 y，将起始节点标记为 x。

   1->2->3->7->6->5->4
   x        y
   

3. 如果 y=middle node AND y!= x.next，则交换 y 和 x.next。然后交换 x 和 x.next。

   1->7->3->2->6->5->4
   x        y
   7->1->3->2->6->5->4
   x        y
   

   将 x 推进两个节点，将 y 推进 1 个节点。

   7->1->3->2->6->5->4
         x     y     
   

4. 现在 if (x != y) { 交换 x 和 y }

   7->1->6->2->3->5->4
         x     y
   

5. 将 x 推进两个节点，将 y 推进 1 个节点

   7->1->3->2->6->5->4
               x  y
   

6. 重复步骤 4 和 5 直到 y 变为 null（到达链表的末尾）或 x == y

所以最后我们得到

7->1->6->2->5->3->4

问题：

有没有更简单的方法来做到这一点？

Answer 1

这是一个简单的解决方案：

1. 找到列表大小。
2. 由 2 个相同的列表溢出。
3. 反转第二部分。
4. 合并列表。

样本：

1. 1->2->3->4->5->6->7 大小是7。（我们应该除以 4 和 3）
2. 拆分为1->2->3->4和5->6->7
3. 反转第二部分1->2->3->4和7->6->5
4. 合并：7->1->6->2->5->3->4

Answer 2

您可以在链表问题问题 17 和 18中找到两个复杂的解决方案。