第 2 关 | 两天写了三次的链表反转 ： 1. 青铜挑战——手写链表反转-灵析社区

时光小少年

链表反转是一个出现频率特别高的算法题，老师过去这些年面试，至少遇到过七八次。其中更夸张的是曾经两天写了三次，上午YY，下午金山云，第二天快手。链表反转在各大高频题排名网站也长期占领前三。比如牛客网上这个No1 好像已经很久了。所以链表反转是我们学习链表最重要的问题，没有之一。


为什么反转这么重要呢？因为反转链表涉及结点的增加、删除等多种操作，能非常有效考察思维能力和代码驾驭能力。另外很多题目也都要用它来做基础， 例如指定区间反转、链表K个一组翻转。还有一些在内部的某个过程用到了反转，例如两个链表生成相加链表。还有一种是链表排序的，也是需要移动元素之间的指针，难度与此差不多。因为太重要，所以我们用一章专门研究这个题目。

LeetCode206 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

本题有两种方法，带头结点和不带头结点，我们都应该会，因为这两种方式都很重要，如果搞清楚，很多链表的算法题就不用做了。

1. 建立虚拟头节点

前面分析链表插入元素的时候，会发现如何处理头结点是个比较麻烦的问题，为此可以先建立一个虚拟的结点ans，并且令ans.next=head，这样可以很好的简化我们的操作。如下图所示，如果我们将链表{1->2->3->4->5}进行反转，我们首先建立虚拟结点ans，并令ans.next=node(1)，接下来我们每次从旧的链表拆下来一个结点接到ans后面，然后将其他线调整好就可以了。

如上图所示，我们完成最后一步之后，只要返回ans.next就得到反转的链表了，代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }
}

建立虚拟结点是处理链表的经典方法之一，虚拟结点在很多工具的源码里都有使用，用来处理链表反转也比较好理解，因此我们必须掌握好。

2. 直接操作链表实现反转

上面的方式虽然好理解应用也广，但是可能会被面试官禁止，为啥？原因是不借助虚拟结点的方式更难，更能考察面试者的能力。

我们观察一下反转前后的结构和指针位置：

我们再看一下执行期间的过程示意图，在图中，cur本来指向旧链表的首结点，pre表示已经调整好的新链表的表头，next是下一个要调整的。注意图中箭头方向，cur和pre是两个表的表头，移动过程中cur经过一次中间状态之后，又重新变成了两个链表的表头。

理解这个图就够了，直接看代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ans = null;
        ListNode cur = head;
        while(cur != null){
             // 将下一个结点保存
            ListNode temp = cur.next;
            // 将当前节点与下一节点断开进行前置
        	cur.next = ans;
            ans = cur;
            // 将当前指针指向下一个位置
            cur = temp;
        }
        return ans;
    }
}

将上面这段代码在理解的基础上背下来，是的，因为这个算法太重要

3. 拓展

上面我们讲解了链表反转的两种方法，带虚拟头结点方法是很多底层源码使用的，而不使用带头结点的方法是面试经常要考的，所以两种方式我们都要好好掌握。

另外这种带与不带头结点的方式，在接下来的指定区间、K个一组反转也采用了，只不过为了便于理解 ，我们将其改成了“头插法”和“穿针引线法”。

拓展 通过递归来实现反转，链表反转还有第三种常见的方式，使用递归来实现，这里不做重点，感兴趣的同学可以研究一下：

public ListNode reverseList(ListNode head) {
	if (head == null || head.next == null) {
		return head;
	}
	ListNode newHead = reverseList(head.next);
	head.next.next = head;
	head.next = null;
	return newHead;
}


阅读量：2013

点赞量：0

收藏量:0