反转和合并链表

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 =中间节点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. 现在，如果（X！= Y）{交换x和y}

   ​​

5. 超前x除以两个节点和y 1个节点

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

6. 重复步骤4并且5直到y变为空（达到链表的末尾）或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。
2. 斯普利特（我们应该4和3分裂）的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

你可以找到Linked list problem问题17和18