题目描述

难度级别：简单

Reverse a singly linked list.

Example:

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

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题思路

迭代

指针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)
};