206. Reverse Linked List

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

Question

Given the head of a singly linked list, reverse the list, and return the reversed list.

第一想法

思路如下：

1. 先记录链表上的值
2. 再次递归链表赋值

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function reverseList(head: ListNode | null): ListNode | null {
    const ret = [];
    const getValues = next => {
        if (!next) return;
        ret.push(next.val);
        getValues(next.next);
    };
    const setValues = next => {
        if (!next) return;
        next.val = ret.pop();
        setValues(next.next);
    };
    getValues(head);
    setValues(head);
    return head;
};

这种方式比较直观，但是效率较低。

递归

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function reverseList(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) {
        return head;
    }
    const tail = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return tail;
};

迭代

思路如下：

1. 每个next指向原来的previous

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function reverseList(head: ListNode | null): ListNode | null {
    let prev = null;
    let crr = head;
    while (crr) {
        const next = crr.next;
        crr.next = prev;
        prev = crr;
        crr = next;
    }
    return prev;
};

End

翻转链表是很基础的操作，一定要熟练掌握多种方式，有助于培养题感。