LeetCode反转链表相关题整理

2021-02-07

综述

最近在面试过程中，连着被问了几次反转链表相关的问题，发现自己虽然知道大体原理，但还是在写到具体细节时会乱掉，加上面试的紧张氛围下，更容易手足无措导致无法正确写出结果，而反转链表是一个非常基础的问题，写不出来会是一个很大的减分

链表节点定义

class ListNode(object):
    def __init__(self, val=0):
        self.val = val
        self.next = None

普通反转链表

url

Leet Code 206 反转链表

难度

Easy

题目

反转一个单链表。

示例:

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

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

题目思考

一种思路，直接建立一个同长度的数组，将遍历出来的节点挨个倒序放入，然后在新的数组上建立新的链表即可

上面这种方法空间复杂度需要O(n)，我们需要一种原地算法，也就是空间复杂度O(1)

如上图所示，我们用pseudo_head作为伪head，指向真正的head，而tail指向当前处理的最后一个节点，tmp作为tail.next的下一个元素，则步骤如下

删除A到C的指向，让A指向D，tail.next = tmp.next
删除C到D的指向，让D指向B，也就是指向第一个节点，tmp.next = head.next
删除head到B的指向，让head指向C，也就是head.next = tmp
此时tail仍然指向A，让新的tmp指向tail的下一个节点，也就是tmp = tail.next

重复以上过程，可以发现问题规模实际是越来越小的，随着tail所指即A的位置的后移，head到A部分的节点已经完成并会保持反转状态

代码

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        pseudo_head = ListNode(0)
        pseudo_head.next = head
        tail = pseudo_head.next
        while tail.next:
            tmp = tail.next
            tail.next = tail.next.next
            tmp.next = pseudo_head.next
            pseudo_head.next = tmp
        return pseudo_head.next

算法分析

只需要一次遍历链表，因此时间复杂度是O(n)

由于只用到了3个变量，且与数据规模无关，因此是原地算法，也就是O(1)

误区分析

在某公司二面中，我写出了如下代码

def reverse(head):
    tail = head.next
    index = 0
    while tail:
        tmp = tail.next
        tail.next.next = head.next
        head.next = tail.next
        tail.next = tmp.next
        tail = tail.next

可以看到，在执行第1步以后，已经丢失了到D的指向
在第2步之后，可以看到此时tmp.next实际是指到了B，而不是我所想的D
此时若让tail.next去指向tmp.next，实际是A指向了B
这样就成了一个head->C->B，A->B，以及D->E

每k个节点进行反转

url

暂未在LeetCode中找到原题

题目

面试中给的变形，给定一个链表，以及数k，每k个节点进行一次反转，不足k个节点的不反转

示例1:

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

示例2:

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

题目思考

假设节点有n个，索引从0, 1, 2, ..., n - 1

对于k，也就是[0, 1, 2, ..., k - 1], [k, k + 1, k + 2, ..., 2k - 1]需要反转，每对k个节点反转后，需要将tail和head指向下一组需要反转的节点，而\(\lfloor \frac{count}{k}\rfloor * k\)开始的所有节点都不需要再做额外处理

代码实现

代码中的l带有伪head节点，tail最初指向的A为索引0

def reverse(l, k):
    count = 0
    p = l
    while p:
        p = p.next
        count += 1
    tail = l.next
    head = l
    index = 0
    while tail.next:
        if index == count // k * k:
            break
        if (index + 1) % k == 0:
            head = tail
            tail = tail.next
        else:
            tmp = tail.next
            tail.next = tail.next.next
            tmp.next = head.next
            head.next = tmp
        index += 1
    return l