[LeetCode] 61. Rotate List

轉自LeetCode

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.

<Solution>

這題用 shift 來理解會比較容易

想像這個 linkedlist 是 circular 的

那麼當 k = 2 的時候，就是往右shift 2 : 4 -> 5 -> 1 -> 2 -> 3

k = 3，就是往右 shift 3 :  3 -> 4-> 5-> 1-> 2

解題想法如下

• 先求出 list 的長度 len

• k 有可能很大，但每 shift len次，等同於沒有移動，所以先把 k = k % len

• 每次都往右 shift 1個位置

• 用 recursive 的方式重複上一個動作，直到要求的 k 次

code 如下

	/**
	* 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 || !head->next || k == 0) {
	return head;
	}
	//> calculate the length
	int len= 0;
	ListNode *cur = head;
	while(cur) {
	cur = cur->next;
	++len;
	}
	//> only need to rotate k % len times
	int target = k % len;
	return rotateRecursive(0, target, head);
	}
	ListNode *rotateRecursive(const int &cnt, const int &target, ListNode *head) {
	if(cnt == target) {
	return head;
	}
	//> find one node befoer tail node
	ListNode *cur = head;
	while(cur->next->next) {
	cur = cur->next;
	}
	//> all nodes shift right by 1
	ListNode *tail = cur->next;
	cur->next = tail->next;
	tail->next = head;
	head = tail;
	return rotateRecursive(cnt+1, target, head);
	}
	};

view raw rotateLinkedList_1.cpp hosted with ❤ by GitHub

那剛剛有提到想像這個 linked list 是 circular 的

其實可以把這個觀念進一步延伸 (參考資料)

想法如下

• 一樣要先計算 list 的長度 len，但計算好的同時，把首尾的 node 也串起來

• 接下來，從 tail node 往前走 len - (k % len) 步，就會到 rotate 後的頭的前一個 node，然後把 head = node->next，node->next = NULL，這樣斷開就找到答案了

code 如下

	/**
	* 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 || !head->next || k == 0) {
	return head;
	}
	//> find length of list
	int len = 1;
	ListNode *curr = head;
	while(curr->next) {
	curr = curr->next;
	len++;
	}
	//> transform to circular list
	curr->next = head;
	//> find the new tail node
	int moveStep = len - (k % len);
	while(moveStep--) {
	curr = curr->next;
	}
	head = curr->next;
	curr->next = NULL;
	return head;
	}
	};

view raw rotateLinkedList_2.cpp hosted with ❤ by GitHub