35.reverse-linked-list.md

206.反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

• 206.反转链表
  • 题目描述
  • 方法 1: 递归
    • 思路
    • 代码
  • 方法 2: 循环
    • 思路
    • 图解
    • 代码

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1: 递归

思路

假设我们已经有了一个 F() 函数，它的功能就是反转链表，然后返回反转后链表的头部。

发现子问题

假设我们有一个链表，这个链表是不是可以分成两个部分：head 和 head.next 到链表尾部。

那要反转这个链表，是不是可以先把 head.next 到链表尾部 这段进行反转，也就是说，要解决 F(head)，我们可以先解决 F(head.next)。

发现大问题和小问题的关系

很简单，只要把反转后的 head.next 到链表尾部 这段的最后一个节点指向 head 就好了。

但是 F() 函数只会返回反转后链表的头部啊，我们怎么知道链表的最后一个节点啊？

在调用 F(head.next) 之前先记录一下 head.next 就好啦，具体看代码注释吧。

递归出口

• 链表最后一个节点：只剩一个节点，直接返回它就好了。
• 空节点。

代码

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    // 递归出口
    if (!head || !head.next) return head;

    // 进行反转下一段链表之前，
    // 先把这段链表的第一个节点记录一下
    // 链表反转结束后，这就变成最后一个节点了
    const lastNode = head.next;

    // 反转余下的链表
    // reverseList 函数会返回反转后链表的头部
    const newHead = reverseList(head.next);

    // 将反转后链表的尾部指向当前节点
    lastNode.next = head;
    head.next = null;
    // 返回新头部
    return newHead;
};

方法 2: 循环

思路

1. 初始化一个 prev 指针为 null，一个 cur 指针为 head；
2. 开始遍历链表，在每一次循环中：

• 先保存 cur.next；
• 把 cur.next 倒转方向指向 prev；
• prev 和 cur 都分别往前一步；

图解

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev, cur = None, head
        while cur != None:
            nextNode = cur.next
            cur.next = prev
            prev = cur
            cur = nextNode
        return prev