灵神基础算法精讲-06-学习笔记

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

用火车来类比链表，链表的第一个节点也叫头节点，可以看成是火车头，其余节点可以看成是车厢，链表的每个节点都包含节点值和指向下一个节点的 next 指针，注意链表的最后一个节点指向空。

如果要反转链表，那么链表的第一个节点，它的 next 应该指向空，链表的其余节点，它们的 next 应该反过来指向它的上一个节点，在实现的时候，需要用变量 cur 表示我们当前遍历到的节点，变量 pre 表示上一个节点。对于链表的第一个节点来说，它的上一个节点是空，我们要做的就是把当前节点的 next 修改成上一个节点，两个变量是不够的，因为一旦修改了当前节点的 next，我们就无法知道它原来的 next 是谁了，所以在修改之前，我们还需要用一个变量 nxt 记录它原来的 next 是谁，这样修改完之后，就可以修改下一个节点了，做法是把 pre 更新成 cur，把 cur 更新成 nxt。如此循环，直到把所有节点都修改完，此时 cur 等于空，pre 等于原来链表的最后一个节点，也就是反转后链表的头节点，最后返回 pre。

做法

def solve(head):
    
    pre = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

92. 反转链表Ⅱ

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

思路

首先记住一个性质，在反转结束后，从原链表上看，pre 指向这一段的末尾，cur 指向这一段的下一个节点，那么将中间这一段反转后，反转后的最后一个节点应该要指向 cur，被反转的这段链表的上一个节点应该要指向 pre，把反转这一段的上一个节点叫做 p0，那么就是把 p0 的 next 指向 cur，然后 p0 指向 pre。

考虑特殊情况，当 left 等于 1 时，我们是没有 p0 的，可以在 head 前面加上一个哨兵节点 dummy，这样 p0 就存在了。

做法

def solve(head, left, right):
    dummy = ListNode(next = head)
    p0 = dummy

    for _ in range(left - 1):
        p0 = p0.next
    
    pre = None
    cur = p0.next

    for _ in range(right - left + 1):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    
    p0.next.next = cur
    p0.next = pre

    return dummy.next

25. K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

由于不足 k 个节点时，是不能翻转的，所以我们可以先把链表长度求出来，翻转之前先判断下剩余节点个数，如果剩余节点数大于等于 k，那么就可以翻转，否则无法翻转，直接退出循环。每一组翻转的过程和上一题是一样的，我们额外要做的事情就是在翻转之后，把 p0 更新成下一段要翻转的链表的上一个节点，它其实就是 p0 的 next，由于我们这里也会修改 p0 的 next，所以在修改之前，可以先用一个临时变量 nxt 把它存起来，最后修改完了再把 p0 更新成 nxt，就可以开启下一轮循环了，然后不断循环就得到答案。最后返回哨兵节点的 next 作为头节点。

做法

def solve(head, k):
    n = 0
    cur = head
    while cur:
        n += 1
        cur = cur.next

    dummy = ListNode(next = head)
    p0 = dummy

    pre = None
    cur = p0.next

    while n >= k:
        n -= k
        for _ in range(k):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
            nxt = p0.next
        p0.next.next = cur
        p0.next = pre
        p0 = nxt

    return dummy.next