JS链表-力扣206反转链表｜刷题打卡

链表总结力扣206题反转链表迭代与递归解法

一、题目描述

反转一个单链表。 示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

二、解题思路

• 迭代

迭代思路很简单，就是从头往后逐个节点翻转链表。 每遍历到一个节点，就将该节点从链表中断开，让这个节点指针指向已反转部分链表。 代码如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head //当链表为空，或链表只有一个节点，则直接返回
    let p = null,z = head,y
    while(z){ // 遍历链表直到该链表为null
        y = z // 使y指向链表头节点，即用y变量存储第一个节点
        z = z.next // 使z指向去掉头节点后的剩余链表
        y.next = p // 将取下来的第一个节点y指针指向已经翻转的链表
        p = y // 使p指向已翻转链表的头节点,即用p来存储已翻转部分的链表
    }
    return p
};

• 递归

递归的思路相对难以理解一点，和迭代不同的是，递归是从后开始翻转：

假如有这么个链表：
5 -> 7 -> 8 -> 4 -> null
当我们递归到4节点时因为该节点next指向null,所以我们默认该节点属于已经翻转的节点，直接返回该节点。
在8这个节点时，4->null默认已经翻转，我们此时要翻转 8 -> 4 -> null 这个链表，我们需要将4节点的next指向8,将8节点的next指向null,即：
8.next = 8.next.next // 8.next指向4节点，4.next=null,所以此处为null
4.next = 8
此时后面的链表部分 4->8->null
同理，递归到7这个节点，我们7节点后面的链表已经递归翻转完成，此时我们不能想的太绕，虽然7后面的链表翻转成为4->8->null,但是
7节点的next还是指向8节点的，而不是指向4节点，所以此时如上
7.next = 7.next.next // 7.next指向8节点，8.next=null,所以此处为null
8.next = 7
此时后面的链表部分 4->8->7->null
于是，重复这个步骤，这个链表就翻转完成。

代码如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head
    let tail = head.next,p = reverseList(head.next) // 此处p会始终返回原链表的最后一个节点，即新链表的第一个节点
    head.next = tail.next // tail为当前head的next,所以此处是将当前head指向null
    tail.next = head // 使当前指向null的head节点成为当前翻转后链表的最后一个节点
    return p // 返回原链表的最后一个节点，即新链表的第一个节点，所以p也代表翻转后的整个链表
    
    // 其实如下这样官方的题解更容易理解一点：
    const p = reverseList(head.next)
    head.next.next = head
    head.next = null
    return p
};

三、总结

这个题，也是一个力扣上的简单题，但是链表的递归还是有点绕的，但递归本质没变，还是从最终的界限开始计算的，也就是从后往前来翻转链表。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情