问题描述

给你单链表的头节点 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循环里面代码的具体含义。

二、代码示例

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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个子问题

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

• 存在最小子问题