Reverse Nodes in k-Group 题解

题目描述

即长为n的列表中，以k（0 < k < n）个元素为一组进行反转，余下不变。
如： 1->2->3->4->5
k = 2: 2->1->4->3->5
k = 3: 3->2->1->4->5

题解

以k个元素为一趟，遍历子链，记录前面结点，后面结点，将当前结点的next指向前面节点即可。
可设置哨兵结点，以消除第一趟的处理。

代码

/**
 * 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) {
        if (k <= 1)
            return head;
        ListNode _node(0), *root = &_node;
        _node.next = head;  // 哨兵结点
        do {
            ListNode *te = head;
            for (int i = k; --i; te = te->next)
                if (!te)
                    return _node.next;
            if (!te)
                return _node.next;
            root->next = te;
            root = head;
            ListNode* prev = te = te->next;
            while (head != te) {
                ListNode* tmp = head->next;
                head->next = prev;
                prev = head;
                head = tmp;
            }
        } while (true);
    }
};

总结

主要是考察指针操作。