letcode 链表-day

24. 两两交换链表中的节点

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

如何 K 个一组反转链表
https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/ru-he-k-ge-d591d/

# 反转区间 [a, b) 的元素，注意是左闭右开
def reverse(a:ListNode, b:ListNode) -> ListNode:
    pre, cur, nxt = None, a, a
    # while  终止的条件改一下就行了
    while cur != b:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    # 返回反转后的头结点
    return pre

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    if not head:
        return None
    # 区间 [a, b) 包含 k 个待反转元素
    a, b = head, head
    for i in range(k):
        # 不足 k 个，不需要反转，base case
        if not b:
            return head
        b = b.next
    # 反转前 k 个元素
    new_head = reverse(a, b)
    # 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k)
    return new_head