给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head) return NULL; if(k == 0) return head; ListNode* p = head; int len = 1; //首先构建环形链表 while(p->next){ // cout << p->val << ","; p = p->next; len++; } //len ++; cout << "len:" << len << endl; p->next = head; //当使用p = head的时候没有形成环形链表,p为最后一个结点指向的空指针next. int i = 0; ListNode* pk = head; int index = 0; //其次对链表进行位移 while(index < len-k%len-1){ cout << pk->val << ","; pk = pk->next; index++; } head = pk->next; //相应位置进行断开 pk->next = NULL; //pk->next = NULL; /* ListNode* tp = head; while(tp){ cout << tp->val << "->"; tp = tp->next; }*/ return head; } };