lintcode-450-K组翻转链表

450-K组翻转链表

给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。

链表元素个数不是k的倍数，最后剩余的不用翻转。

样例

给出链表 1->2->3->4->5

k = 2, 返回 2->1->4->3->5

k = 3, 返回 3->2->1->4->5

标签

链表脸书

思路（使用栈，空间复杂度O(k)）

一个简单的方法是，使用一个栈记录一组待翻转数

首先用 end 指针定位一组数的尾部，begin 定位一组数的首部，在定位尾部时将结点值入栈
若栈的大小等于 k，表示这组数可以翻转，便从 begin 开始，将此节点值改为栈顶元素，并出栈

code

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    /*

     * @param head: a ListNode

     * @param k: An integer

     * @return: a ListNode

     */

    ListNode * reverseKGroup(ListNode * head, int k) {

        // write your code here

        if (k <= 0 || head == NULL || head->next == NULL) {

            return head;

        }

        stack<int> stack;

        ListNode *begin = head, *end = head;

        while (end != NULL) {

            for (int i = 0; i < k && end != NULL; i++) {

                stack.push(end->val);

                end = end->next;

            }

            if (stack.size() == k) {

                for (int i = 0; i < k; i++) {

                    begin->val = stack.top();

                    begin = begin->next;

                    stack.pop();

                }

            }

        }

        return head;

    }

};

巴特西

lintcode-450-K组翻转链表

450-K组翻转链表

样例

标签

思路（使用栈，空间复杂度O(k)）

code

最新文章

热门文章