leetcode/25ZReverse_Nodes_in_k-Group

25. Reverse Nodes in k-Group

给定一个链表, 每次反转链表数量为k的节点, 然后返回更改后的链表

k是一个正整数, 小于等于链表的长度, 如果链表的长度不是k的整数倍, 最后遗漏的节点保持原样

my code

/**
 * 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 (!head) return NULL;

        ListNode* ret = head;
        while (head && head->next) {
            int kt = k;
            ListNode* headt = head;
            vector<int> vec;

            vec.push_back(headt->val);
            while (--kt && head->next) {
                head = head->next;
                vec.push_back(head->val);
            }
            head = head->next;

            if (kt) break;
            reverse(headt, vec);
        }

        return ret;
    }

private:
    void reverse(ListNode* head, vector<int>& vec) {
        for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {
            head->val = *it;
            head = head->next;
        }
    }
};

这道题的思路很清晰, 感觉不应该是hard难度的题

简单地将链表每一部分分开, 然后调用反序函数就可以了

可以优化的点是 while 那里, 以及我可以不用在 while 中判断, reverse 应该能够正常处理元素数量不同的情况

那么我在最后做一次判断, 将最后一次不用修改的还原就可以了, 这样可以省去 while 中的判断逻辑

速度上来说还算不错, 但是资源使用率上就很堪忧了

dalao’s code

class Solution {
public:
    ListNode* reverse(ListNode* first, ListNode* last)
    {
        ListNode* prev = last;

        while ( first != last )
        {
            auto tmp = first->next;
            first->next = prev;
            prev = first;
            first = tmp;
        }

        return prev;
    }

    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        auto node=head;
        for (int i=0; i < k; ++i)
        {
            if ( ! node  )
                return head; // nothing to do list too sort
            node = node->next;
        }

        auto new_head = reverse( head, node);
        head->next = reverseKGroup( node, k);
        return new_head;
    }
};

这个做法和我的想法基本相同, 但是在细节上的处理很好

首先, 他采用的递归, 这样代码更加简洁易懂

其次循环中是更改链表的指向, 而不是赋值, 这样功能性更强