反转链表

用户4456933

发布于 2021-06-01 15:06:58

84200

代码可运行

文章被收录于专栏：用户4456933的专栏用户4456933的专栏

运行总次数：0

代码可运行

难度：简单来源：206. 反转链表

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路：

定义输出链表 prev；
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用；
顺序遍历链表 head , 将其中的元素移入链表 prev ；
图解如下；
而递归的思路其实就是传递 2 个参数，prev 和 curr ，分别用来指定反转后和前的链表，思路是差不多的。

题解一：迭代

/**
 * 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) {
    // 方法一：迭代实现
    let prev = null
    let curr = head
    while (curr != null) {
        let next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
};

题解二：递归

/**
 * 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) {
    const reverse = (prev, curr) => {
        if (!curr) {
            return prev
        }
        let next = curr.next
        curr.next = prev
        return reverse(curr, next)
    }
    return reverse(null, head)
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法