图解 LeetCode 链表: 206. Reverse Linked List

今天是 LeetCode 算法的 第 1 阶段第 5 天 ，这一阶段主要学习链表相关的算法题和链表数据结构。今天的题目是反转单链表，这道题面试被问到的几率很大，网上有些资料解释的不太清楚，我今天给你把它讲明白了。

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

分析

题目要求给定一个单链表，把单链表反转一下。举个例子，军训的时候，教官向我们下达指令“向后转”，其实可以把这一动作看做是一次单链表的反转过程。下面这张图中的士兵向后旋转一下，既是一次单链表的旋转。

单链表反转后如下图所示：

代码

在实现的时候有点抽象，当前节点 curr 的 next 指向前一个节点 prev，prev逐渐向后移动，cur 也向后移动，直到为 NULL。一图胜千言

C++ 实现如下：

ListNode* reverseBetween(ListNode* head) {
    LstNode *prev = NULL;
    ListNode *curr = head;
    while (curr) {
    // 保存下一个节点，防止断链
    ListNode *nextTemp = curr->next;
    // 让当前节点的下一个指向前一个
    curr->next = prev;
    // 移动前一个位置
    prev = curr;
    // 遍历下一个子串
    curr = nextTemp;
  }
  return prev;
}

结果

Runtime: 8 ms, faster than 100.00% of C++ online submissions for Reverse Linked List. Memory Usage: 9.3 MB, less than 14.43% of C++ online submissions for Reverse Linked List.

总结

这道题的关键点是让后一个节点的 next 指向它的前一个节点，在整个排序过程中需要防止断链。它的思想特别简单，你一下子就能想到整个排序的过程，但是当你写代码的时候会发现很多问题。试试写一下代码吧！

文中涉及到的算法代码，我在GitHub创建了一个项目 LeetCodeGraphically，点击阅读原文即可查看。

下一道题目留给你思考：

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL