lintcode 170. Rotate List

class Solution { public: /** * @param head: the List * @param k: rotate to the right k places * @return: the list after rotation */ ListNode * rotateRight(ListNode * head, int k) { // write your code here if(head == NULL || head->next == NULL){ return head; } int len = 0; ListNode *copy = head; while(head != NULL){ len++; head = head->next; } int realK = k % len; if(realK == 0){ return copy; } ListNode *copy2 = copy; for(int i = 0; i < len - realK - 1; i++){ copy = copy->next; } ListNode *newHead = copy->next; copy->next = NULL; ListNode *newHeadCopy = newHead; while(newHead->next != NULL){ newHead = newHead->next; } newHead->next = copy2; return newHeadCopy; } };

二刷 2019年03月30日11:18:08
ListNode * rotateRight(ListNode * head, int k) { // write your code here // k 可能大于list的长度，所以要先遍历一遍找到 list长度。然后 k % list长度。 // 找到rotate的节点。拆，重建。 if(head == NULL){ return head; } ListNode *copy = head; int len = 0; while(head != NULL){ ++len; head = head->next; } int newK = k % len; if(newK == 0){ return copy; } ListNode *pre = copy; for(int i = 0; i < len - k - 1; i++){ pre = pre->next; } //重建 ListNode *newHead = pre->next; pre->next = NULL; ListNode *newHeadCopy = newHead; while(newHead->next != NULL){ newHead = newHead->next; } newHead->next = copy; return newHeadCopy; }