面试算法：单链表反转

给定一个单链表 list，请将它反转后返回，示例：

原链表：

反转链表：

定义的单链表结点类结构如下：

/**
 * 单向链表结点
 */
public class ListNode {

    public Integer value;

    public ListNode next;

    public ListNode() {

    }

    public ListNode(int value) {
        this.value = value;
    }
}

我们先写两个方法，用于组装成链表和将链表打印到控制台，方便进行算法结果验证：

/**
 * 组装成链表
 */
public ListNode assemble(int[] items) {
    if (items == null || items.length == 0) {
        return null;
    }

    ListNode list = new ListNode(items[0]);
    ListNode node = list;
    for (int i = 1; i < items.length; i++) {
        node.next = new ListNode(items[i]);
        node = node.next;
    }
    return list;
}

/**
 * 将链表打印到控制台
 */
public void print(ListNode list) {
    if (list == null) {
        System.out.print("<空>");
    }
    while (list != null) {
        System.out.print(list.value + " -> ");
        list = list.next;
    }
    System.out.println("null");
}

1. “栈”反转

“栈”是一种先进后出 (FILO)的数据结构，我们可以利用它的这个特性来实现反转链表。

1）先将链表结点顺序入栈：

2）然后开始将结点出栈，并逐一反转指针指向：

为了能在最后返回反转链表，我们给栈顶结点使用一个top结点引用来指向它，通过top结点，能够在完成反转链表后，按顺序访问到完整的反转链表的所有结点；此外，为了在出栈的时候，能反转指针指向，另外定义多两个结点prev和rear，初始prev和top指向同一个结点栈顶结点，即反转链表的首结点。

先将栈顶的原链表尾结点（反转链表首结点）5出栈：

将结点4出栈（rear结点），并反转指针指向4 -> 5为5 -> 4，此时结点4指向NULL，即不指向任何一个实结点：

prev结点往后顺移一个结点位置，此时指向结点4，并将结点3出栈（rear结点），然后反转指针指向3 -> 4为4 -> 3：

prev结点往后顺移一个结点位置，此时指向结点3，并将结点2出栈（rear结点），然后反转指针指向2 -> 3为3 -> 2：

prev结点往后顺移一个结点位置，此时指向结点2，并将结点1出栈（rear结点），然后反转指针指向1 -> 2为2 -> 1：

Done.

3）代码实现：

public ListNode reverseByStack(ListNode list) {
    // 结点为空，或者只有单结点，不需要反转
    if (list == null || list.next == null) {
        return list;
    }

    // Deque 双端队列可以实现“栈”数据结构功能
    Deque<ListNode> stack = new LinkedList<>();
    while (list != null) {
        // 逐一入栈：stack.addFirst(list);
        stack.push(list);
        list = list.next;
    }

    // 出栈栈顶结点
    ListNode top = stack.pop();
    ListNode prev = top, rear;
    while (!stack.isEmpty()) {
        // 逐一出栈：rear = stack.removeFirst();
        rear = stack.pop();

        // 反转指针
        prev.next = rear;
        rear.next = null;

        // prev 结点指针往后顺移一个结点位置
        prev = rear;
    }
    return top;
}

4）结果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseByStack(list);
System.out.print("反转单链表：");
print(rlist);

原始单链表：16 -> 24 -> 48 -> 43 -> 4 -> 9 -> 47 -> 42 -> null
反转单链表：42 -> 47 -> 9 -> 4 -> 43 -> 48 -> 24 -> 16 -> null

2. 递归法

将原链表的结点按顺序一直递归到最后一层，也就是原链表的尾结点，将尾结点引用透传返回至递归方法第一层，在每一层里，将结点指针指向逆转，然后方法返回。注意：当链表长度太长时，这种方式会抛出 java.lang.StackOverflowError。

1）将原链表的结点按顺序一直递归到最后一层，将尾结点`5`返回：

2）尾结点`5`透传返回，并在每一层中，反转指针指向：

尾结点5使用rlist引用指向它，注意在反转指针指向的时候，不能使用rlist引用来操作，因为在每一层递归中，rlist都要保证是往上“透传”的，也就是说它永远是5结点。

反转指针指向4 -> 5为5 -> 4，此时结点4指向NULL，即不指向任何一个实结点：

反转指针指向3 -> 4为4 -> 3：

反转指针指向2 -> 3为3 -> 2：

反转指针指向1 -> 2为2 -> 1：

Done.

3）代码实现：

public ListNode reverseRecursively(ListNode list) {
    // 结点为空，或者只有单结点，不需要反转
    // 注意：递归函数的最后一层也会在这里返回：list.next == null
    if (list == null || list.next == null) {
        return list;
    }

    // 递归函数透传返回最后一个结点的引用到上一层
    ListNode rlist = reverseRecursively(list.next);
    // 在递归函数的每一层，rlist 引用透传返回上一层之前，反转当前递归层次的两个结点的指针指向，即原 list -> list.next 的反转为 list.next -> list
    list.next.next = list;
    list.next = null;
    return rlist;
}

4）结果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseRecursively(list);
System.out.print("反转单链表：");
print(rlist);

原始单链表：44 -> 28 -> 3 -> 11 -> 49 -> 3 -> 20 -> 13 -> null
反转单链表：13 -> 20 -> 3 -> 49 -> 11 -> 3 -> 28 -> 44 -> null

3. 就地逆置（单指针法）

这种方法比较好理解，就是将链表的所有结点按顺序迭代，并且在每一次迭代时，调整指针指向。需要增加两个指针引用prev和rear，分别用于定位当前链表结点的前一个结点和后一个结点，以方便进行指针指向调整操作。

1）定义`prev`和`rear`结点引用，按顺序迭代链表结点：

初始化prev指向NULL，rear未指向任何结点：

rear指向2结点（当前结点list的下一结点），调整指针指向1 -> 2为1 -> NULL，并将prev和list往后顺移一个结点位置（此时prev指向1，list指向2）：

rear指向3结点（当前结点list的下一结点），调整指针指向2 -> 3为2 -> 1，并将prev和list往后顺移一个结点位置（此时prev指向2，list指向3）：

rear指向4结点（当前结点list的下一结点），调整指针指向3 -> 4为3 -> 2，并将prev和list往后顺移一个结点位置（此时prev指向3，list指向4）：

rear指向5结点（当前结点list的下一结点），调整指针指向4 -> 5为4 -> 3，并将prev和list往后顺移一个结点位置（此时prev指向4，list指向5）：

rear指向NULL结点（当前结点list的下一结点），调整指针指向5 -> NULL为5 -> 4，并将prev和list往后顺移一个结点位置（此时prev指向5，list指向NULL）：

Done.

2）代码实现：

public ListNode reverseInSitu1(ListNode list) {
    // 结点为空，或者只有单结点，不需要反转
    if (list == null || list.next == null) {
        return list;
    }

    // list 为当前结点，prev 为 list 的前一个结点，rear 为 list 的后一个结点
    ListNode prev = null, rear;
    while (list != null) {
        // 1、暂存最后一步将要操作 list 结点指针往后顺移一个结点位置的 rear 结点引用（最后一步会赋值：list = rear;）
        rear = list.next;

        // 2、反转指针指向，即原 prev -> list 的反转为 list -> prev
        list.next = prev;

        // 3、prev 和 list 结点指针依次往后顺移一个结点位置
        prev = list;
        list = rear;
    }
    return prev;
}

3）结果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseInSitu1(list);
System.out.print("反转单链表：");
print(rlist);

原始单链表：11 -> 12 -> 2 -> 15 -> 17 -> 38 -> 10 -> 1 -> null
反转单链表：1 -> 10 -> 38 -> 17 -> 15 -> 2 -> 12 -> 11 -> null

4. 就地逆置（双指针法）

这种方法跟上一种方法比较类似，不同的是，当前结点list在每一次迭代时，并不会往后顺移一个结点位置，而是指向rear结点（当前结点list的下下一结点），此方法比“单指针法”少一次迭代。需要增加两个指针引用prev和rear，分别用于定位当前链表结点的前结点（初始等于当前结点）和后结点，以方便进行指针指向调整操作。

1）定义`prev`和`rear`结点引用，按顺序迭代链表结点：

初始化prev指向1（和list指向同一个结点），rear未指向任何结点：

rear指向3结点（当前结点list的下下一结点），调整指针指向2 -> 3为2 -> 1，将prev往后顺移一个结点位置（此时prev指向2），然后将list指针指向3（即1 -> 2调整为1 -> 3，打破上一个指针指向调整形成的1 -> 2 -> 1的“环”）：

rear指向4结点（当前结点list的下下一结点），调整指针指向3 -> 4为3 -> 2，将prev往后顺移一个结点位置（此时prev指向3），然后将list指针指向4（即1 -> 3调整为1 -> 4，打破上一个指针指向调整形成的1 -> 3 -> 2 -> 1的“环”）：

rear指向5结点（当前结点list的下下一结点），调整指针指向4 -> 5为4 -> 3，将prev往后顺移一个结点位置（此时prev指向4），然后将list指针指向5（即1 -> 4调整为1 -> 5，打破上一个指针指向调整形成的1 -> 4 -> 3 -> 2 -> 1的“环”）：

rear指向NULL结点（当前结点list的下下一结点），调整指针指向5 -> NULL为5 -> 4，将prev往后顺移一个结点位置（此时prev指向5），然后将list指针指向NULL（即1 -> 5调整为1 -> NULL，打破上一个指针指向调整形成的1 -> 5 -> 4 -> 3 -> 2 -> 1的“环”）：

Done.

可以看到，“双指针法”的第一个指针用于反转指针指向，但这会形成一个“环”，而第二个指针就是为了打破这个环，同时指向下一个操作的结点（rear结点引用就是为了保存它，以便在每次迭代的最后一步中list可以找到并指向它）。

2）代码实现：

public ListNode reverseInSitu2(ListNode list) {
    // 结点为空，或者只有单结点，不需要反转
    if (list == null || list.next == null) {
        return list;
    }

    // list 为当前结点，prev 为 list 的前结点（初始等于当前结点），rear 为 list 的后结点
    ListNode prev = list, rear;
    while (list.next != null) {
        // 1、暂存最后一步将要操作 list -> rear 转向的 rear 结点引用（最后一步会赋值：list.next = rear;）
        rear = list.next.next;

        // 2、第 1 次调整指针指向（3 个结点之间的第 2 个指针），即原 list.next -> rear 的调整为 list.next -> prev，注意此步会形成“环”
        list.next.next = prev;

        // 3、prev 结点指针往后顺移一个结点位置，此时 prev 结点指针指向反转单链表的首结点
        prev = list.next;

        // 4、第 2 次调整指针指向（3 个结点之间的第 1 个指针），list 结点指针指向 rear 结点，即 list -> rear，此步用于打破第 2 步中形成的“环”
        list.next = rear;
    }
    return prev;
}

3）结果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseInSitu2(list);
System.out.print("反转单链表：");
print(rlist);

原始单链表：25 -> 38 -> 50 -> 47 -> 16 -> 30 -> 27 -> 40 -> null
反转单链表：40 -> 27 -> 30 -> 16 -> 47 -> 50 -> 38 -> 25 -> null

5. 头插法

头插法是在每次插入新元素时，插入到一个被称为“头结点”的元素的后面的方法，在 JDK 7 的 java.util.HashMap 类中也有应用。

1）定义一个临时“头结点”`tmpHead`，`rear`结点引用，按顺序迭代链表结点，并将它们插入到`tmpHead`的后面：

初始化临时头结点tmpHead，rear结点引用未指向任何结点：

rear指向2结点（当前结点list的下一结点），将结点1插入到tmpHead后面（结点NULL前面），将当前结点list往后顺移一个结点位置（此时list指向2）：

rear指向3结点（当前结点list的下一结点），将结点2插入到tmpHead后面（结点1前面），将当前结点list往后顺移一个结点位置（此时list指向3）：

head_2.png

rear指向4结点（当前结点list的下一结点），将结点3插入到tmpHead后面（结点2前面），将当前结点list往后顺移一个结点位置（此时list指向4）：

rear指向5结点（当前结点list的下一结点），将结点4插入到tmpHead后面（结点3前面），将当前结点list往后顺移一个结点位置（此时list指向5）：

rear指向NULL结点（当前结点list的下一结点），将结点5插入到tmpHead后面（结点4前面），将当前结点list往后顺移一个结点位置（此时list指向NULL）：

Done.

2）代码实现：

public ListNode reverseByHeadInsertion(ListNode list) {
    // 结点为空，或者只有单结点，不需要反转
    if (list == null || list.next == null) {
        return list;
    }

    // list 为当前结点，tmpHead 为一个临时头结点，rear 为 list 的后一个结点
    ListNode tmpHead = new ListNode(), rear;
    while (list != null) {
        // 1、暂存最后一步将要操作 list 结点指针往后顺移一个结点位置的 rear 结点引用（最后一步会赋值：list = rear;）
        rear = list.next;

        // 2、向反转链表头部 tmpHead 后插入新结点（当前结点）
        list.next = tmpHead.next;
        tmpHead.next = list;

        // 3、当前结点 list 指针往后顺移一个结点位置
        list = rear;
    }
    return tmpHead.next;
}

3）结果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseByHeadInsertion(list);
System.out.print("反转单链表：");
print(rlist);

原始单链表：6 -> 24 -> 39 -> 7 -> 27 -> 37 -> 22 -> 36 -> null
反转单链表：36 -> 22 -> 37 -> 27 -> 7 -> 39 -> 24 -> 6 -> null

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,602评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,442评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,878评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,306评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,330评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,071评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,382评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,006评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,512评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,965评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,094评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,732评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,283评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,286评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,512评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,536评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,828评论 2赞 345

面试算法：单链表反转

1. “栈”反转

1）先将链表结点顺序入栈：

2）然后开始将结点出栈，并逐一反转指针指向：

3）代码实现：

4）结果验证：

2. 递归法

1）将原链表的结点按顺序一直递归到最后一层，将尾结点5返回：

2）尾结点5透传返回，并在每一层中，反转指针指向：

3）代码实现：

4）结果验证：

3. 就地逆置（单指针法）

1）定义prev和rear结点引用，按顺序迭代链表结点：

2）代码实现：

3）结果验证：

4. 就地逆置（双指针法）

1）定义prev和rear结点引用，按顺序迭代链表结点：

2）代码实现：

3）结果验证：

5. 头插法

1）定义一个临时“头结点”tmpHead，rear结点引用，按顺序迭代链表结点，并将它们插入到tmpHead的后面：

2）代码实现：

3）结果验证：

推荐阅读更多精彩内容

1）将原链表的结点按顺序一直递归到最后一层，将尾结点`5`返回：

2）尾结点`5`透传返回，并在每一层中，反转指针指向：

1）定义`prev`和`rear`结点引用，按顺序迭代链表结点：

1）定义`prev`和`rear`结点引用，按顺序迭代链表结点：

1）定义一个临时“头结点”`tmpHead`，`rear`结点引用，按顺序迭代链表结点，并将它们插入到`tmpHead`的后面：