图解LeetCode——剑指 Offer 24. 反转链表

一、题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

二、示例

示例:

【输入】 1->2->3->4->5->NULL
【输出】 5->4->3->2->1->NULL

限制：

• 0 <= 节点个数 <= 5000

三、解题思路

本题给出的数据结构是单向链表，那么链表中的每个节点ListNode只有2个变量，即：

【int val】表示当前节点存储的值。
【ListNode next】表示当前节点的后置节点的引用。

那么既然是单向链表，我们遍历链表中所有结点的时候，就只能通过调用ListNode.next的方式逐一向后遍历节点，遍历方式当然不是问题的难点，难点是如何进行翻转呢？

其实针对翻转的操作，我们只会涉及到相邻的两个节点，即：当前节点和它的next节点；那么，我们需要去做如下两个操作，就可以完成翻转了：

【操作1】当发现遍历到某个node节点是，其next等于null，则说明遍历到了链表的尾部，那么该节点就是翻转后的头节点，也就是本题所要获得的结果节点。
【操作2】在递归遍历操作之后，执行head.next.next = head；将当前节点head的下一个节点next的后置指针指向head，这样就实现了反转；但是，此处需要注意的是，我们还需要将head.next设置为null，因为这个对于原链表的头节点很重要（因为它变为了新链表的尾节点，其next指针应该被设置为null）

解题思路说完了，我们举例，尝试将Node(1)——>Node(2)——>Node(3)——>Node(4)——>Node(5)这个链表执行翻转操作。具体操作如下图所示：

四、代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; // 凤尾变龙头
        ListNode result = reverseList(head.next);
        head.next.next = head; // 翻转链表
        head.next = null;
        return result;
    }
}

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

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

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