反转链表也是面试时常问到的题目，题目听上去很简单，想要快速正确的写出来，也确实需要很扎实的基本功。
这类简单的题目既有非递归的实现方法，也有递归的实现方法。
非递归实现
非递归实现，模拟的是基本的手动操作， 访问链表中的每一个节点，但是同时要记住当前被访问节点的上一个和下一个节点。这三个指针构成了一个滑动的窗口，当前的值是滑动窗口的中心，上一个节点最终会变成新链表的头节点。代码如下：
public void Reverse() { p = this.Head; node prev = null; while(p != null) { node next = p.next; p.next = prev; prev = p; p = next; } this.head = prev; }递归实现
第一条：每次递归都能将问题规模缩减下来
第二条： 对应递归终止条件，递归必须有个出口，不然会陷入无限递归当中
第三条： 顺着自己的思路，将递归问题细分为更小的递归问题，然后再进行递归调用。
伪代码如下：
Result M(Problem prob) { if (<problem can be solved easily>)/*对应终止条件*/ return <easy solution>; // The problem cannot be solved easily.//对应一般情况，再一步进行细分，递归调用 Problem smaller1 = <reduce problem to smaller problem>//缩小问题规模 Result result1 = M(smaller1); Problem smaller2 = <reduce problem to smaller problem>////缩小问题规模 Result result2 = M(smaller2); ... Result finalResult = <combine all results of smaller problem to solve large problem>//综合结果 return finalResult; }
归纳法来分析这个题目：
Reverse(first) = { if (first == null) return null; if (first.next == null) return first; Node newHead = reverse(first-> next); first.next.next = first; first.next = null; return newHead; }下面是反转链表的递归实现：
public void ReverseRecursive() { this.Head = ReverseInternal(this.Head); } private Node ReverseInternal(Node fromNode) { if (fromNode == null) { return null; } if (fromNode.Next == null) { return fromNode; } Node rest = ReverseInternal(fromNode.Next); fromNode.Next.Next = fromNode; fromNode.Next = null; return rest; }
转载于:https://www.cnblogs.com/xuyanran/p/8227341.html
