首页 > 代码库 > Leetcode--Reverse Nodes in k-Group

Leetcode--Reverse Nodes in k-Group

Problem Description:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

分析:看到这个题目第一想法就是就地操作,依次以k个元素为一组来逆置,最后少于k个元素的组不逆置,但是实际操作时将前后两组的首尾相连不是很好操作,于是直接利用栈将k个元素进栈出栈实现逆置,具体实现时先统计出链表的总元素个数,提前算出需要逆置的组数,代码如下:

/**
 * 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 *p=head,*newh=NULL,*pre; 
		stack<ListNode *> stk;
        int len=0,i=1,cnt,n;
        while(p)
        {
            len++;
            p=p->next;
        }
        if(k>len||k<=1)
            return head;
        n=len/k;
        p=head;
        while(i<=n)
        {
            cnt=0;
			while(cnt<k)
			{
				stk.push(p);
				p=p->next;
				cnt++;
			}
			while(!stk.empty())
			{
				if(!newh)
				{
					newh=stk.top();
					pre=newh;
					stk.pop();
				}
				else
				{
					pre->next=stk.top();
					pre=pre->next;
					stk.pop();
				}
			}            
            i++;
        }
        pre->next=p;
        return newh;
    }
};