面试算法题：链表的倒转

具体的代码调试和讲解，请参看视频：
如何进入google,算法面试技能全面提升指南

在算法面试中，链表出现的频率相当之高，一是因为链表是数据结构的基础，很多更复杂的高层数据结构的设计大多基于链表之上。其次，链表可以实现多种变化，因此使用链表来考察候选人，既能考察其技术基本功是否扎实，同时又能检验对方的思维灵敏性，因此，链表作为算法面试的常用手段也就不足为奇了。

有一道链表面试题，在我的面试经历中出现过很多次，也被很多知名的软件巨头用来招过人，虽然我遇见多次，但每次做该题的时候，总是不能解答到点子上。因此也无法在面试中得到高分，因此我觉得有必要把这道题拿出来进行详细的分析，让大家不要像我一样在面试中错失良机。

题目是这样的，给定一个链表，让你把链表实现反转。例如

1 -> 2 -> 3 -> 4 -> 5

反转成以下情形：

5 -> 4 ->3 -> 2 -> 1.

这道题初看起来似乎很简单，我当时的做法是这样的，想必有不少人的想法跟我一样，假定链表的数据结构如下：

class Node {
    int val;
    Node next;
}

我当时的想法是依赖三个指针来实现反转操作，指针p1指向第一个节点，指针p2指向第二个节点, 指针p3指向第三个节点，把p2.next 指向 p1, 然后p1 挪到p2, p2挪到p3, p3 挪到它的下一个节点，也就是：

 p1 = node1
 p2 = node1.next;
 p3 = p2.next

 p2.next = p1;
 p2 = p3;
 p1 = p2;
 p3 = p3.next;

上面的操作一直进行，知道遍历完整个链表为止。上面的办法是可行的，只不过答不到点上，面试官想看的不是这个做法。况且上面做法复杂，要考虑很多情况，例如要判断指针是否为空，要判断链表是否有三个以上的节点等等。我每次遇到这道题，都采用上面的做法，做完了都以为自己答的好，但面试结果总不是很理想，后来想到更好的解决办法后才知道面试不好的原因。

这道题其实有更简单，更巧妙的做法，假定链表已经转变为以下情况：

1 -> 2 <- 3 <- 4 <- 5

也就是从第一个结果开始，后面的节点已经导致完毕，接下来我们要做的，就是简单的一步，只要把节点1和2之间的指向关系倒转一下就可以了。于是这样就能形成一种递归的思路，如果我要导致的链表，有n 个节点，那么如果第一个节点后面的 n-1 个节点已经正确倒转了的话，我只要处理第一和第二个节点的指向关系就可以了。要使得后n-1个节点正确导致，那么先使得后n-2个节点正确导致，于是就这么递归下去，最后只剩下一个节点时，什么都不用做就已经倒转好了，这种思路简单明了，不需要像第一种一样考虑各种边界条件，这种做法才是面试官真正想要的，我们看看代码：

public class Node {
    public int val;
    Node next;
}


public class ListUtility {
    Node createList(int nodeNum) {
        if (nodeNum <= 0) {
            return null;
        }
        
        Node head = null;
        int val = 0;
        Node node = null;
        
        while (nodeNum > 0) {
            
            if (head == null) {
                head = new Node();
                head.val = val;
                node = head;
            } else {
                node.next = new Node();
                node = node.next;
                node.val = val;
                node.next = null;
            }
            
            val++;
            nodeNum--;
        }
        
        return head;
    }
    
    public void printList(Node head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        
        System.out.println("null");
    }
}

Node 仅仅用来表示一个链表节点，ListUtility的作用是生成一个用于操作的链表，同时当给定链表头节点时，把链表打印出来。真正实现链表倒转作用的是下面代码：

public class ListReverse {
    private Node head;
    private Node newHead;
    
    public ListReverse(Node head) {
        this.head = head;
    }
    
    private Node recursiveReverse(Node node) {
        if (node == null || node.next == null) {
            newHead = node;
            return node;
        }
        
        Node head = recursiveReverse(node.next);
        head.next = node;
        node.next = null;
        
        return node;
    }
    
    
    public Node getReverseList() {
         recursiveReverse(head);
         return newHead;
    }
}

recursiveReverse做的就是递归性的去反转链表，如果当前只有一个节点，那么链表就已经反转完毕，如果不止一个节点，那么先把当前节点后面的链表反转，然后改变当前节点后下一个节点的指向关系，原来是当前节点的next指针指向下个节点，现在改成下个节点的next指针指向当前节点。

上面代码实现简洁，不用像开始使用三个指针时那样去考虑各种特色情况。由于反转过程只需遍历一次链表的所有节点，因此算法的复杂度是O(N).

我们看看运行结果：

public class LinkList {
    public static void main(String[] args) {
        ListUtility util = new ListUtility();
        Node head = util.createList(10);
        util.printList(head);
        
        ListReverse reverse = new ListReverse(head);
        util.printList(reverse.getReverseList());
    }
}

上面代码，先是生成含有10个节点的队列，并打印出来，然后把队列反转后再次打印出来，运行后结果如下：

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null

通过运行结果可知，我们的算法设计是正确的。