关键点

  1. 反转单链表采用穿针引线法
  2. pre在过程中起链接作用, 初始时tail是前一组的尾部,结束时tail是当前组的尾部
  3. head初始为头节点,反转后为链表尾节点
  4. 没什么好说的,不熟练就多做几遍,直到5分钟内写出来(无bug)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummynode = new ListNode(-1);
        dummynode->next = head;
        ListNode *tail = dummynode, *pre = dummynode;
        while (tail->next) {
            for (int i = 0; i < k && tail != nullptr; i++) {
                tail = tail->next;
            }
            if (tail == nullptr) break;
            ListNode *tmp = tail->next;
            tail->next = nullptr;
            pre->next = reverseList(head);
            head->next = tmp;
            pre = tail = head;
            head = tmp;
        }

        return dummynode->next;
    }

    ListNode *reverseList(ListNode *head) {
        ListNode *dummynode = new ListNode(-1);
        dummynode->next = head;
        ListNode *cur = head;
        while (cur->next) {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = dummynode->next;
            dummynode->next = tmp;
        }

        return dummynode->next;
    }
};
最后修改:2021 年 03 月 30 日 10 : 12 AM