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