凌云的博客

LeetCode 算法题 25. K 个一组翻转链表

分类：algorithm| 发布时间：2016-07-17 15:36:00

---

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明:

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解法 1，使用栈缓存

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode *tail = &dummy;
        stack<ListNode*> s;
        while (head) {
            int i = 0;
            for (; head && i < k; ++i) {
                s.push(head);
                head = head->next;
            }

            if (i == k) {
                for (; i > 0; --i) {
                    tail->next = s.top();
                    tail = tail->next;
                    s.pop();
                }

                tail->next = head;
            }
        }

        return dummy.next;
    }
};

这种解法的思路很直观，先将 K 个节点缓存在堆栈中，然后再一一翻转，缺点是不符合使用常量空间的要求。

解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;

        int times = k;
        ListNode* p,*q,*r,*former;
        r = nullptr;
        former = &dummy;
        p = q = head;
        while (p) {
            r = q->next;
            while (--times) {
                if (!r) {// 不够k个了，翻转回来
                    r = q->next;
                    q->next = nullptr;
                    while (q != p) {
                        reverse(q, r);
                    }
                    former->next = p;
                    return dummy.next;
                    }
                reverse(q, r);
            }

            former->next = q;
            former = p;
            p = q = r;
            times = k;
        }

        former->next=nullptr;
        return dummy.next;
    }

    void reverse(ListNode *&p, ListNode *&q) {
        auto tmp = q->next;
        q->next = p;
        p = q;
        q = tmp;
    }
};

思路为 K 个节点一组进行翻转，如果发现剩下的节点不足 K 个则重新翻转回来。