【C++刷题】优选算法——链表

链表常用技巧和操作总结

• 常用技巧
  画图
  引入虚拟头节点
  不要吝啬空间，大胆定义变量
  快慢双指针
• 常用操作
  创建一个新节点
  尾插
  头插

1. 两数相加

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
   int carry = 0;
    ListNode* newHead = new ListNode, *cur = newHead;
    while (l1 != nullptr && l2 != nullptr) {
        int num = l1->val + l2->val + carry;
        carry = num / 10;
        num = num % 10;
        cur->next = new ListNode(num);
        cur = cur->next;
        l1 = l1->next;
        l2 = l2->next;
    }
    while (l1 != nullptr) {
        int num = l1->val + carry;
        carry = num / 10;
        num = num % 10;
        cur->next = new ListNode(num);
        cur = cur->next;
        l1 = l1->next;
    }
    while (l2 != nullptr) {
        int num = l2->val + carry;
        carry = num / 10;
        num = num % 10;
        cur->next = new ListNode(num);
        cur = cur->next;
        l2 = l2->next;
    }
    if (carry != 0) {
        cur->next = new ListNode(carry);
    }
    return newHead->next;
}

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

ListNode* swapPairs(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode *front = head, *back = front->next, *newHead = new ListNode, *cur = newHead;
    while (true) {
        cur->next = back;
        ListNode* tmp = back->next;
        back->next = front;
        front->next = tmp;
        cur = front;
        if (tmp != nullptr && tmp->next != nullptr) {
            front = tmp;
            back = front->next;
        } else if (tmp != nullptr && tmp->next == nullptr) {
            cur->next = tmp;
            return newHead->next;
        } else {
            return newHead->next;
        }
    }
}

3. 重排链表

ListNode* reverse(ListNode* head) {
   if (head == nullptr || head->next == nullptr) return head;

    ListNode* newHead = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}
void reorderList(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* cur1 = head, *cur2 = reverse(slow);
    ListNode* newHead = new ListNode, *cur = newHead;
    while (cur1 != cur2 && cur2 != nullptr) {
        cur->next = cur1;
        cur1 = cur1->next;
        cur = cur->next;

        cur->next = cur2;
        cur2 = cur2->next;
        cur = cur->next;
    }
}

4. 合并 K 个升序链表

// 解法一
ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 小根堆
    priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
    for (ListNode* e : lists) {
        if (e != nullptr) {
            pq.push(e);
        }
    }
    
    ListNode *newHead = new ListNode, *cur = newHead;
    while (!pq.empty()) {
        cur->next = pq.top();
        cur = cur->next;
        pq.pop();

        if (cur->next != nullptr) {
            pq.push(cur->next);
        }
    }

    return newHead->next;
}

// 解法二
ListNode* merge_sort(vector<ListNode*>& lists, int start, int end) {
    if (start > end) return nullptr;
    else if (start == end) return lists[start];

    int mid = start + (end - start) / 2;
    ListNode* left = merge_sort(lists, start, mid);
    ListNode* right = merge_sort(lists, mid + 1, end);

    if (left == nullptr) return right;
    else if (right == nullptr) return left;

    ListNode *newHead = new ListNode, *cur = newHead;
    while (left != nullptr && right != nullptr) {
        if (left->val < right->val) {
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    }
    while (left != nullptr) {
        cur->next = left;
        left = left->next;
        cur = cur->next;
    }
    while (right != nullptr) {
        cur->next = right;
        right = right->next;
        cur = cur->next;
    }

    return newHead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    return merge_sort(lists, 0, lists.size() - 1);
}

5. K 个一组翻转链表

ListNode* reverseKGroup(ListNode* head, int k) {
    int total = 0;
    ListNode* cur = head;
    while (cur != nullptr) {
        ++total;
        cur = cur->next;
    }
    ListNode* newHead = new ListNode;
    cur = newHead;
    while (head != nullptr) {
        int count = k;
        ListNode* tail = head;
        if (total >= k) {
            while (count-- && head != nullptr) {
                ListNode* tmp = head->next;
                head->next = cur->next;
                cur->next = head;
                head = tmp;
            }
            total -= k;
        }

        cur = tail;
        if (total < k) {
            cur->next = head;
            break;
        }
    }
    return newHead->next;
}