Rotate List
A not so fun problem: https://leetcode.com/problems/rotate-list/description/
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4 Output:2->0->1->NULLExplanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right:0->1->2->NULLrotate 4 steps to the right:2->0->1->NULL
I'm doing it in 2n-time: I do count the number of elements in the list, use it to mod the k, and then do another loop to find the precise pointers to use to reshape the list. Some of the "off by one" calculations in problems like this just give them a "meh" connotation. Still, here it is for reference. Cheers, Marcelo.
public class Solution
{
public ListNode RotateRight(ListNode head, int k)
{
if (head == null) return head;
int count = 0;
ListNode last = null;
for (ListNode n = head; n != null; last = n, n = n.next, count++) ;
k %= count;
if (k == 0) return head;
ListNode prevPrev = null;
ListNode prev = head;
ListNode front = head;
while (front != null)
{
if (k > 0)
{
k--;
}
else
{
prevPrev = prev;
prev = prev.next;
}
front = front.next;
}
if (prevPrev != null)
{
prevPrev.next = null;
last.next = head;
head = prev;
}
return head;
}
}
I love lists :)
ReplyDeleteclass Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr || k == 0) return head;
int length = 0;
ListNode* last;
for (auto temp = head; temp != nullptr; temp = temp->next, length += 1) {
last = temp;
}
if (k > length) k %= length;
if (k == length || k == 0) return head;
auto temp = head;
for (int i = 0; i < length - k - 1; ++i, temp = temp->next) {}
auto new_start = temp->next;
temp->next = nullptr;
last->next = head;
return new_start;
}
};
https://gist.github.com/ttsugriy/af17db45adb87ab506e4dc44ab6cab4d