图解LeetCode——206. 反转链表

一、题目

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

二、示例

2.1> 示例 1：

【输入】head = [1,2,3,4,5]
【输出】[5,4,3,2,1]

2.2> 示例 2：

【输入】head = [1,2]
【输出】[2,1]

2.3> 示例 3：

【输入】head = []
【输出】[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

三、解题思路

3.1> 思路1：迭代方式

针对链表反转操作，我们首先可以选择采用迭代的方式进行转换，即，每当遍历两个节点的时候，我们都将next指针反转执行前置节点即可，此处需要注意的是，由于我们要修改next指针，所以，遍历的时候，我们要先将原本的next指针指向的对象进行缓存，然后再改变next指针。这么做的目的就是为了继续可以向后去执行遍历操作。具体操作方式请见下图所示：

3.2> 思路2：递归方式

根据题目描述，我们要将原链表执行翻转操作。那么，由于单向链表的单一方向性，我们如果想翻转链表，可以采取递归的方式进行处理，具体逻辑如下所示：

【步骤1】每次递归都要将head.next节点作为方法的入参进行传递。
【步骤2】当传入的节点为null或者它的next节点为null，则直接返回该节点。
【步骤3】当遍历到最后一个节点的时候，就可以进行两个节点之间的链表反转操作了。

四、代码实现

4.1> 实现1：迭代方式

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, temp = null;
        while (head != null) {
            temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

4.2> 实现2：递归方式

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

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」