【基础算法】反转链表的三种方法

一、通过迭代来实现链表反转

通过迭代来实现链表的反转，我们需要三个变量：

1. curr：保存当前节点，初始保存的是head（头结点）
2. prev：保存当前节点的前一个节点，初始为null
3. next：保存当前节点的后一个节点，初始为head.next

那我们怎么通过这三个变量来实现链表的反转呢？让我们先看一下实现步骤：

**注意：**好，我们的链表当next==null时，链表也正确的完成了反转。

​ 那我们前面所疑惑的问题：为什么当我们递归之前要进行一次反转也就不言而喻了。因为，如果我们不在递归前进行一次反转的话，最后一次我们会少反转一个节点（当递归反转结束后，会丢失原始链表中的尾节点）。

二、通过递归来实现链表反转

通过递归来实现链表的反转，我们只需要将一个待反转的链表看作两部分：

1. 一个未被反转的节点：

   第一次递归中，这个节点就是原始链表的头结点【head】。

2. 一个已经完成反转的链表：

   第一次递归中，这个链表是除了原始链表的头结点，其余节点所完成反转后的链表【这个当前链表的尾节点是 head.next】

同样，链表反转的过程，我们通过画图来说明：

怎么样？递归反转我们也学会了，是不是也并没有多么复杂。我们只是通过最终的结果来反推子结果，再通过子结果再继续反推，直到反推到已排序的节点只有一个时，我们也就可以一步步得到上一步的结果，最终的实现我们整个链表的反转。

三、通过头插法来实现链表反转

通过头插法来实现链表的反转，与迭代反转一样，也需要三个变量来保留待插节点、待插节点的前一个节点、待插节点的下一个节点。

在画图之前，我们先思考一个问题：头插法实现链表反转他是怎么实现的呢？我们就想象一下，这个带反转的链表它只有两个节点，head和head.next，我们怎么将这个链表来实现反转呢？

是不是只需要先让head插在null上，再让head.next插在head上就实现了反转。

那我们再继续思考，为什么需要三个变量呢？

第一次，我们让head.next=null时，我们需要一个变量a=null吧

我们需要让一个变量b=head吧，此时我们就可以让head.next=null了，但是注意，如果这时直接让head.next=null，那么原始链表中head后的其他节点就全部丢失了

所以，我们还需要一个变量c=head.next吧。

好我们来捋一下顺序

a=null;
b=head;
c=head.next;
b.next=a; // 实现了head.next=null

来，我们继续思考，怎么让head.next.next=head？

一样的，需要一个变量a=head，一个变量b=head.next，那还需要一个变量c=head.next.next？没错需要变量c=head.next.next（对于我们两个节点的链表而言，这个c此时为null）

a=head;
b=head.next;
c=head.next.next; // 这个我们先不确定，可能需要这个变量
b.next=a; // 实现head.next.next=head

我们观察上述两个代码块，思考这是不是可以写一个循环啦？

a=null;
while(循环条件){
	b=head;
    head=head.next;
    b.next=a;
}

我们继续思考循环条件是什么，或者这个循环什么时候退出呢？

是不是当head==null的时候，退出循环？

我们通过画图来进行验证：

好，我们通过画图实现了链表的反转，也可以看到我们上面写的循环是有点问题，那我们做一些改变，并将变量重新命一下名。

...
head // 头结点
...
// newHead就是那个a变量
// temp就是那个b变量
Node newHead=null, temp;
while(head!=null){
    temp=head;
    head=head.next;
    temp.next=newHead;
    newHead=temp;
}

代码实现

package edu.hrbu.test;

/**
 * @author 徐登宇
 */
public class TestReverseLink {

    // 链表节点的数据结构
    private static class Node{
        private int data; // 当前节点的值
        private Node next; // 当前节点指向的下一个节点

        public Node(int data){
            this.data=data;
        }
    }

    // 构建链表并返回头结点
    private static Node createLink(){
        Node head = new Node(1);
        Node n1 = new Node(2);
        Node n2 = new Node(3);
        Node n3 = new Node(4);
        Node n4 = new Node(5);
        head.next=n1;
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        return head;
    }

    // 打印链表
    private static void printLink(Node head){
        // 如果链表只有一个节点，直接打印该节点的值
        if (head.next==null) System.out.println(head.data);
        while (head!=null){
            System.out.print(head.data+" -> ");
            head=head.next;
        }
    }

    /**
     * 通过迭代来实现链表反转
     *
     * 需要用到三个变量，
     *   prev：保存当前节点的前一个节点
     *   curr：保存当前节点
     *   next：保存当前节点的下一个节点
     *
     * 具体怎么实现链表反转？
     *
     *
     *
     * @param head 原始链表头结点
     * @return 链表反转后的新的头结点
     */
    private static Node reverseWithIterate(Node head){
        // 如果链表没有节点或只有一个节点，直接返回
        if (head==null||head.next==null) return head;

        // 需要三个变量保存我们当前走到的节点以及它的前一个节点和后一个节点
        Node prev=null; // 当前节点的前一个节点，反转被指向的节点
        Node curr=head; // 当前节点
        Node next=head.next; // 当前节点的下一个节点，用来判断链表是否走到头，并用来保留原始链表
        // 在循环反转之前，我们先进行一次反转
        curr.next=prev;
        // 进行循环反转
        while (next!=null){
            prev=curr;
            curr=next;
            next=next.next;

            // 反转
            curr.next=prev;
        }
        return curr;
    }

    /**
     * 通过递归方法来实现链表反转
     *
     * 需要一个变量来存储反转后的链表的头结点【新的头结点】
     *
     * 怎么通过递归实现链表反转的呢？
     *   一、将未反转的链表看作两部分：1. 原始的头结点；2. 已经实现反转的新链表【我们要接收这个新链表的头结点，最后将最终的新链表的头结点返回出去】
     *   二、让原始链表头结点的下一个节点执行这个原始链表的头结点，并将原始的头结点的next置为空，这样原始链表的头结点就成为了反转后的链表的尾节点，实现了最终的链表的反转。
     *
     * @param head 原始链表头结点
     * @return 链表反转后的新的头结点
     */
    private static Node reverseWithRecursive(Node head){
        // 递归结束条件：只有一个节点（或者头结点为空，直接不进行递归直接返回）
        if (head==null||head.next==null) return head;

        // 怎么通过递归实现链表反转的？
        // 将原始未反转的链表看作两部分：一个原始链表的头结点，一个已经完成反转的链表。
        // 那么，只需要将已经完成反转的链表的尾节点，也就是原始头节点原始指向的下一个节点的next指向原始的头结点，并将原始的头结点的next置空，让原始头结点变为反转后的链表的尾节点，就完成了链表的反转。

        // 我们需要一个变量，来接收反转后的链表的头结点，最后将这个反转后的链表的头结点返回就可以了
        Node newHead=reverseWithRecursive(head.next);
        // 让head的下一个节点反过来指向head
        head.next.next=head;
        // 将head的next置空
        head.next=null;
        return newHead;

    }

    /**
     * 通过头插法来实现链表反转
     *
     * 需要三个变量：
     *   1. 作为每次反转时被指向的节点，最后被作为完成反转的链表的头结点返回；
     *   2. 作为头插时被插入的头结点
     *   3. 作为保存后续节点的作用，并起到判断是否走到链表最后的作用【可以用原始链表的头结点实现这些个作用：每次循环head=head.next就可以】
     *
     *
     * @param head 原始链表头结点
     * @return 链表反转后的新的头结点
     */
    private static Node reverseWithHeadInsert(Node head){
        // 当链表只有一个节点，或者没有节点时，直接返回
        if (head==null||head.next==null) return head;

        // 头插法实现链表反转，也需要三个变量
        // 1. 作为反转后的新的头结点，每次头插最后指向新插上的头结点
        // 2. 作为临时节点，实现头插的作用，作为临时的头结点
        // 3. 【我们将原始链表的头结点作为这个变量就可以】作为是否走到链表最后的条件，以及实现保存原始链表的节点的作用
        Node newHead=null,temp;
        while (head!=null){
            temp=head;
            head=head.next;
            temp.next=newHead;
            newHead=temp;

        }
        return newHead;

    }


    public static void main(String[] args) {
        Node head = createLink();
        System.out.println("反转前：");
        printLink(head);
        System.out.println("\n反转后：");
//        head=reverseWithIterate(head);
//        head=reverseWithRecursive(head);
        head=reverseWithHeadInsert(head);
        printLink(head);
    }

}