今日面试题：乾坤大挪移；及颠倒乾坤的分析

arron刘

今日面试题：乾坤大挪移

给定一个单向链表，设计一个算法实现链表向右旋转k个位置。K是非负的整数。这题看起来简单，可真编程实现有陷阱啰。

举例：

给定：1->2->3->4->5->6->null 并且k=3，

则有：4->5->6->1->2->3->null

颠倒乾坤分析：http://bbs.chinaunix.net/thread-4093152-1-1.html

题目：

在一棵二叉搜索树中，有两个节点颠倒了顺序。要求实现一个算法，在不改变树结构的前提下，恢复正确的二叉搜索树。给出一个空间为O(n)的实现很容易，那该如何给出一个空间O(1)的实现呢？

分析：

首席，从一个实例来看，如果两个节点颠倒顺序，会发生什么。

这是一颗正常的BST

              7

             / \

            4   10

           / \    \

          2   6   13

         / \

        1   3

       /

      0

看看几种情况：

假设同一枝上的两个节点相邻颠倒了，比如0和1，那么中序遍历后的结果变成

1，0，2，3，4，6，7，10，13

在这种情况下，显然1和0的顺序不对，那么要交互他们的顺序。

如果同一枝上不相邻的两个节点，比如，1和4呢？

0，4，2，3，1，6，7，10，13

在此情形下，4和2，3和1的顺序不对，这时，需要将前面不对的4，和后面不对的1，交换顺序。

如果是左右枝中的元素呢，比如，2和10

0，1，10，3，4，6，7，2，13

这时，10和3，7和2的顺序不符，这时，需将前面不符的10，和后面不符的2，交换。

再看，如果是根节点参与呢，比如7，和0，

7，1，2，3，4，6，0，10，13

这时7和1，6和0，不符从小到大的顺序，同理，需颠倒7和0。

至此，各种情况我们都考虑了，而且归纳出基本的想法是：

用中序遍历，记录顺序不符的对。如果只有一对元素不符，交换他们；如果有两对不符，那么将第一对中的前一个元素，和第二对中的后一个元素，互换。

如果采用基于递归和堆栈的中序遍历，空间要求会是O(n)，显然不符合题意。那么，我们需要寻求能用O(1)空间进行中序遍历的方法。

arron刘

单向链表算法