反转链表(合集)

反转链表I

ListNode *reverseList(ListNode *head) {
		// 最重要的一步，增加一个空节点，这样整个流程会顺畅很多
    ListNode* pre = nullptr;
    ListNode* cur = head;
    // 边界条件要注意，最后一步的时候，cur 指向空，而 pre 指向反转后的头节点
    while (cur != nullptr) {
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

反转链表II

ListNode *reverseBetween(ListNode *head, int left, int right) {
    // 设置虚拟头节点，解决 left=1 的情况
    ListNode dummy(0);
    dummy.next = head;

    ListNode *p0 = &dummy;
    for (int i = 0; i < left - 1; i++) {  // p0默认对应1的正确位置，如果从left开始，要向右移动 left-1 次
        p0 = p0->next;
    }

    // 开始反转
    ListNode *pre = p0;
    ListNode *cur = p0->next;
    for (int i = 0; i < right - left + 1; i++) { // 从2到4进行反转，需要反转3个节点
        ListNode *nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }

    // 更新头尾
    p0->next->next = cur;
    p0->next = pre;
    return dummy.next;
}

反转链表III（K个一组反转链表）

ListNode *reverseKGroup2(ListNode *head, int k) {
    // 计算链表长度
    int n = 0;
    ListNode *cur = head;
    while (cur != nullptr) {
        n++;
        cur = cur->next;
    }
    // 哨兵节点
    ListNode dummy(0);
    dummy.next = head;
    ListNode *p0 = &dummy;
    ListNode *pre = nullptr;
    cur = p0->next;
    // K个一组进行反转, 不足k个的不反转
    while (n >= k) {
        n -= k;
        for (int i = 0; i < k; i++) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        ListNode *nxt2 = p0->next;
        p0->next->next = cur;
        p0->next = pre;
        p0 = nxt2;
    }
    return dummy.next;
}