K个一组反转链表

LIZHAO • • LeetCode
阅读量 0 次 • 评论量 0 个

Leetcode: K个一组翻转链表

掌握程度：★ ☆ ☆

第一反应，使用双指针，两个指针的距离就是需要翻转的组。

反转链表的函数

首先应该有一个可以反转一个范围内的元素的函数。

std::tuple<ListNode *, ListNode *> reverse(ListNode *head, ListNode *tail) {
    //反转，prev 指的是要将后面的元素接到上面的元素。
 	//既然是反转，那就要反着看待。
    ListNode *prev = tail->next;
    //tmp 用来移动
    ListNode *tmp = head;

    while (prev != tail) {
        ListNode *next = tmp->next;
        tmp->next = prev;
        prev = tmp;
        tmp = next;
    }
    return {tail, head};
}

使用双指针遍历

为了避免边界的特殊判断，使用一个dummy的结点指向head。

ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode *hair = new ListNode(0);
    hair->next = head;
	//这里正向的遍历，pre很好理解，就是前面的元素。
    ListNode *pre = hair;

    while (head != nullptr) {
        ListNode *tail = pre;
        //移动tail
        for (int i = 0; i < k; ++i) {
            tail = tail->next;
            if (tail == nullptr) {
                return hair->next;
            }
        }

        //保存尾后
        ListNode *next = tail->next;

		//反转局部链表
        auto [tHead, tTail] = reverse(head, tail);
		//连接翻转后的前后结点，并移动head
        pre->next = tHead;
        tTail->next = next;
        pre = tTail;
        head = next;
    }
    return hair->next;
}
喵~