【进阶篇 - Day 35】 2020-12-05 -反转链表系列（07. 高频面试题 ）

题目描述

入选理由

1. 面试考察频率高

题目描述

206. 反转链表 (opens new window) > 92. 反转链表 II (opens new window) > 25. K 个一组翻转链表 (opens new window)

我的回答

https://github.com/leetcode-pp/91alg-2/issues/61#issuecomment-739113692

反转链表

递归

var reverseList = function (head) {
    if (!head || !head.next) return head

    let last = reverseList(head.next)
    head.next.next = head
    head.next = null
    return last
};

迭代

var reverseList = function (head) {
    if (!head || !head.next) return head
    let [pre, curr] = [null, head]
    while (curr) {
        const temp = curr.next
        curr.next = pre
        pre = curr
        curr = temp
    }
    return pre
};

反转链表 2

这里的问题就是找到 m-n 之间的链表进行反转

所以抽离出来的 reverserN 在最后一个 next 要将原来的 next 接上去就形成了一个反转完的链表

let sameNode
var reverserN = function (head, n) {
    if (n === 1) {
        sameNode = head.next
        return head
    }
    let last = reverserN(head.next, n - 1)
    head.next.next = head
    head.next = sameNode
    return last
}
var reverseBetween = function (head, m, n) {
    if (m === 1) {
        return reverserN(head, n)
    }
    head.next = reverseBetween(head.next, m - 1, n - 1)
    return head
};

K 个一组翻转链表

// TODO:K 个一组翻转链表

大概思路是看懂了 ，先复习别的去了

参考回答

• [官方题解](https://github.com/leetcode-pp/91alg-2/blob/master/solution/advanced/d35 link.md)