Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

C++:
01 /**
02  * Definition for singly-linked list.
03  * struct ListNode {
04  *     int val;
05  *     ListNode *next;
06  *     ListNode(int x) : val(x), next(NULL) {}
07  * };
08  */
09 class Solution {
10 public:
11     ListNode *rotateRight(ListNode *head, int k) {
12         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14        if((k==0)||(head==NULL))
15         return head;
16        queue<int> A;
17        stack<int> B;
18        for(ListNode* p=head;p!=NULL;p=p->next)
19        {
20            B.push(p->val);
21        }
22        while(!B.empty())
23        {
24            int tmp=B.top();
25            B.pop();
26            A.push(tmp);
27        }
28        for(int i=0;i<k;i++)
29        {
30           int tmp=A.front();
31           A.pop();
32           A.push(tmp);
33        }
34        ListNode* hd=NULL;
35        ListNode* prv=NULL;
36        while(true)
37        {
38            if(A.empty())
39            {
40                hd=prv;
41                break;
42            }
43            int t=A.front();
44            A.pop();
45            ListNode* tmp=new ListNode(t);
46            tmp->next=prv;
47            prv=tmp;
48        }
49        return hd;
50     }
51 };
Advertisements
This entry was posted in Array and linked list, Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s