LeetCode - 25. Reverse Nodes in k-Group

简介: 25. Reverse Nodes in k-Group Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个链表和一个k值,将链表按照k个结点为一组,组内翻转.

 25. Reverse Nodes in k-Group

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定一个链表和一个k值,将链表按照k个结点为一组,组内翻转.

analyse:

继续抖机灵!

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-19-11.06
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

// 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)
    {
        vector < int > ve;
        ListNode * tptr = head;
        while( head)
        {
            ve . push_back( head -> val);
            head = head -> next;
        }

        if( ve . size() < k) return tptr;
        delete( head);
        int frontIndex = 0 , backIndex = k - 1;
        while( frontIndex < ve . size() && backIndex < ve . size())
        {
            int low = frontIndex , high = backIndex;
            while( low < high)
            {
                swap( ve [ low ], ve [ high ]);
                ++ low , -- high;
            }
            frontIndex = backIndex + 1;
            backIndex += k;
        }

        int isFirst = 1;
        ListNode * res = nullptr , *p = nullptr;
        for( int i = 0; i < ve . size(); ++ i)
        {
            if( isFirst)
            {
                isFirst = 0;
               p = new ListNode( ve [ i ]);
                res =p;
            }
            else
            {
               p -> next = new ListNode( ve [ i ]);
               p =p -> next;
            }
        }
        return res;
    }
};

int main()
{
    Solution solution;
    int n , k;
    while( cin >>n >> k)
    {
        bool isFirst = 1;
        ListNode * res = nullptr , * head = nullptr;
        for( int i = 0; i <n; ++ i)
        {
            int tmp;
            cin >> tmp;
            if( isFirst)
            {
                isFirst = 0;
                head = new ListNode( tmp);
                res = head;
            }
            else
            {
                head -> next = new ListNode( tmp);
                head = head -> next;
            }
        }
        ListNode * ans = solution . reverseKGroup( res , k);
        while( ans)
        {
            cout << ans -> val << " ";
            ans = ans -> next;
        }
        cout << "End." << endl;
    }
    return 0;
}
/*

*/
目录
相关文章
Leetcode 24.Swap Nodes in Pairs
 给你一个链表,交换相邻两个节点,例如给你 1->2->3->4,输出2->1->4->3。   我代码里在head之前新增了一个节点newhead,其实是为了少写一些判断head的代码。
41 0
|
索引
LeetCode 345. Reverse Vowels of a String
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
104 0
LeetCode 345. Reverse Vowels of a String
|
机器学习/深度学习 NoSQL
LeetCode 344. Reverse String
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
99 0
LeetCode 344. Reverse String
LeetCode 190. Reverse Bits
颠倒给定的 32 位无符号整数的二进制位。
92 0
LeetCode 190. Reverse Bits
LeetCode 150. Evaluate Reverse Polish Notation
根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
47 0
LeetCode 150. Evaluate Reverse Polish Notation
LeetCode 92. Reverse Linked List II
给定一个链表,反转指定的子序列.
82 0
LeetCode 92. Reverse Linked List II
|
机器学习/深度学习 NoSQL 算法
LeetCode 344. 反转字符串 Reverse String
LeetCode 344. 反转字符串 Reverse String
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List
LeetCode之Reverse String II
LeetCode之Reverse String II
117 0
LeetCode之Reverse String
LeetCode之Reverse String
103 0