链表常见面试题：反转链表

链表常见面试题：反转链表

问题描述

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

示例1:

---

输入: head = [1,2,3,4,5]

输出: [5,4,3,2,1]

示例2:

输入: head = [1,2]

输出: [2,1]

一、问题分析

这道题常见的解法有两种：双指针迭代 和 递归。

方法一：双指针迭代

1. 申请两个指针，第一个指针叫 prev，最初是指向 null 的。

2. 第二个指针 curr 指向 head，然后不断遍历 curr。

3. 每次迭代到 curr，都将 curr的 next 指向 prev，然后 prev 和 curr 前进一位。

4. 都迭代完了(curr 变成 null 了)，prev 就是最后一个节点了,同时也是新链表的头结点。

接下来一步步分析，首先定义指针：

//定义前置指针
 ListNode prev = null;
 //定义cur指针
 ListNode curr = head;

相应的图解如下：

初始的链表状态：

然后开始移动指针，进行第一次遍历，按照上面分析里的1,2步骤移动后的的结果如下图：

继续移动指针，进行第二次遍历，指针继续按照上面分析里的1,2步骤移动后的的结果如下图： 

继续移动指针，进行第三次遍历，指针继续上面分析里的1,2步骤移动后的的结果如下图：

接下来结合代码来看，逐步理解while循环里面代码的具体含义。

二、代码示例

class Solution {
    public ListNode reverseList(ListNode head) {
        //极值判断
        if(head == null || head.next ==null){
            return head;
        }

        //定义前置指针
        ListNode prev = null;
        //定义cur指针
        ListNode curr = head;

        //开始遍历链表
        while (curr != null){
            //把当前curr指向的节点的下一个节点暂存起来，用于curr的下一次移动
            ListNode next = curr.next;
            //把当前curr指向下一个节点，指向prev
            curr.next = prev;
            //prev指针向前移动一个节点，即指向curr
            prev = curr;
            //当前curr指向的节点，向前移动一个节点，即指向next
            curr = next;
        }
        //此时对于反转完成的链表，pre来到了链表的头结点，返回即可
        return prev;
    }
}

方法二：递归

使用递归有三个先决条件：

• 大问题可以拆解为N个子问题

• 子问题的求解方式和大问题相同

• 存在最小子问题

反转链表恰好符合这三个条件。我们可以把反转整个链表拆解为反转N个子链表，同时反转子链表与反转整个链表的解题方法相同，存在反转链表节点的最小子问题。

所以我们尝试一下采用递归的思想来解题：

1.  使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点ret。

2. 每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。

3. 同时让当前结点的 next 指针指向 null，从而实现从链表尾部开始的局部反转。

4. 当递归函数全部出栈后，链表反转完成。

可以结合下面的图解进行理解。

1.链表未反转之前：

2.递归到链表的最后一个结点，进行反转：

 3.继续反转，直到当前节点为null或者当前节点的下一个节点为null，标志着反转结束。

看一下递归的代码。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //递归找到链表的最后一个节点，并作为反转后的头节点
        ListNode ret = reverseList(head.next);

        //让当前节点的下一个节点的next指针指向当前节点，也就是进行两个节点之间的指针指向反转
        head.next.next = head;

        //把当前节点的next指针指向null
        head.next = null;
        return ret;
    }
}

总结

反转链表是道很经典的链表题，同时也是链表类型的入门级题目，所以很有必要好好掌握。双指针迭代解法虽然比递归简单些，但是我觉得双指针对理解链表指针的移动很有帮助，值得研究一下。不过两种解法最好都掌握。下篇文章还是反转链表的题型，不过有些难度。

写在最后

本人还维护了微信公众号，里面会持续输入包括但不仅限：算法，计算机网络，MySQL，大数据相关组件等。欢迎踊跃关注，万分感谢！！！

附上二维码：