反转单链表

简介

    这是一个相对比较简单直接的问题。假设我们有这么一个单链表，需要将它反转过来。对它分析的过程结合图的形式来看会比较清晰直观一点。

 

分析

    我们要通过遍历的方式来反转链表，那么就需要考虑每次反转的时候需要将当前元素指向它原来的前面一个元素。因此，我们需要有一个变量来保存要反转元素的前面一个元素。另外，我们在遍历的时候，要调整当前元素时，为了能够找到后面的结点，需要用到一个额外的变量来指向调整元素，同时调整完之后保证指向前面的元素转而指向当前。

    这么个过程显得比较晦涩，用图表的方式来看就很直观了。

    假定我们有一个链表，并且声明了两个变量，prev, temp：

 

 

     在开始的时候，temp = null, prev = null。接着，我们将temp = head; 这样temp就指向head当前的位置，同时将head指向它下一个位置，也就是head = head.next; 由于我们假定prev表示当前元素的前一个元素。开始的时候prev = null， 我们当前的这个元素是temp所指向的。我们再将temp.next = prev；这样就将第一个元素给反转过来了。如下图所示：

 

 

     当然，为了紧跟head这个元素。prev本身必须是head的前一个，所以在前面一步的设置完成后，我们需要将prev跟进。正好temp指的是当前的，那么就需要将prev = temp。这样结果就如下图了：

 

    这样，经过前面几个步骤，我们就已经将第一个元素给反转过来了。后面的过程也类似。假设我们要接着反转第二个元素，那么它的过程如下图：

 

 

     这一步骤相当于执行了这么两句：temp = head; head = head.next;

     这一步则是将temp所指向的元素反转，也就是：prev = temp.next;

     有了前一步的过程，这一步就是相当于要将prev跟上，也就是：prev = temp;

    ok, 有了前面的这两轮走下来，我们发现他们所要调整的步骤主要如下：

    1. temp = head; // 指定当前要调整的点。

    2. head = head.next; // 走向下一个要被调整的点

    3. temp.next = prev; // 将当前的点反转

    4. prev = temp; // 表示当前调整结点的前一个结点跟进

    以上的4个步骤构成了一个循环。循环的终止条件是head == null；这样，我们很快可以得到一个单链表反转的方法：

public static Node reverse(Node head)
{
    Node prev = null;
    Node temp = null;
    while(head != null)
    {
        temp = head;
        head = head.next;
        temp.next = prev;
        prev = temp;
    }
    return temp;
}

总结

    单链表反转的过程并不复杂，只是它的过程如果不仔细整理清楚的话容易出错。用画图描述每个小步骤的方法可以帮助理请思路。 

 

补充

    反转单链表的方法当然不止前面那一种，还有几种比较常见的，比如说借助堆栈的方式来实现；新建一个链表，每次在表头插入原有链表的元素以及一种递归的方式。这里就对这几种方式也增加一个辅助的分析。

辅助堆栈

    整个的过程其实还是比较简单，我们从原有链表头开始，遍历所有的元素，遍历中将每次碰到元素都压入堆栈。结束这个过程后再将堆栈的元素依次弹出来，重新构造一个新的链表。一种大致的实现代码如下：

Node reverse(LinkedList list)
{
    Node node = list.head;
    Stack<Node> stack = new Stack<Node>();
    while(node != null)  // 所有元素入栈
    {
        stack.push(node);
    }

    Node newHead, item;
    if(!stack.empty())
    {
        newHead = stack.pop();
        item = newHead;
     }
    // 再将元素出栈重新构造
    while(!stack.empty())
    {
        Node temp = stack.pop();
        item.next = temp;
        item = item.next;
    }

    return newHead;
}

 

新建链表

    新建链表的方式也比较简单，首先建立一个空的链表，然后将在遍历原来链表元素的时候每次将元素从新链表的头元素后面插入。

Node reverse(LinkedList list)
{
    LinkedList newList = new LinkedList();
    Node item = list.head;
    while(item != null)
    {
        item.next = newList.head.next
        newList.head.next = item;
    }

    return item.head;
}

    这里假定已经定义好了LinkedList和Node的数据类型。

 

递归

    除了前面采用的方法，实际上还有一种办法，就是递归的方式。在这里，我们假定定义了一个全局访问的成员head，可以作为返回的链表头。递归的方法考虑的一个关系如下：如果我们当前的元素不是到了链表的尾部，则递归到下一层。这样一直到原来链表的末尾，我们将当前元素的引用设置为全局head。在每一层递归返回的时候，将它设置为后面元素的next引用。一种参考代码的实现如下：

Node head = null;

void reverse(Node head)
{
    if(node.next != null)
    {
        reverse(node.next);
        node.next.next = node;
    }
    else
    {
        head = node;
        return;
    }
}

    总的来说，实现一个链表的反转其实方法还是挺多的。各种方法的思路确实都有其特点。

参考资料

Introduction to algorithms