反转链表

原创

_kyle

修改于 2020-12-09 10:18:24

79300

代码可运行

文章被收录于专栏：kyle的专栏kyle的专栏

运行总次数：0

代码可运行

题目

难度级别：简单

反转一个单链表。

示例:

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

进阶:

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

解题思路

迭代

指针prev遍历链表head，通过中间节点保存prev的下一项，修改prev.next为node以后，把prev重新赋值给node，最后指针重新指向保存的节点prev.next。

const reverseList = function(head) {
    if (!head || !head.next) return head 
    
    let prev = head
    let node = null

    while(prev) {
        let tempNode = prev.next
        
        prev.next = node
        node = prev
        prev = tempNode
    }
    
    return node
};

简化代码

const reverseList = function(head) {
    if (!head || !head.next) return head 
    let [prev, node] = [head, null]

    while(prev)
        [prev.next,node,prev] = [node,prev,prev.next]
    
    return node
};

递归

把需要调整方向的看成头head和next已经调整好方向的链表，依次将head的next赋值为null，next的next赋值为head。

const reverseList = function(head) {
    if (!head || !head.next) return head 
    let next = head.next
    let reverseHead = reverseList(next)
    
    head.next = null
    next.next = head

    return reverseHead
};

使用array.reduce

通过将链表元素存入数组中，最后遍历数组，通过reduce将链表反转。

const reverseList = function(head) {
    if (!head || !head.next) return head 
    const arr = []

    while(head) {
        arr.push(head.val)
        head = head.next
    }
    
    return arr.reduce((acc,v) => ({val: v, next: acc}), null)
};