## Saturday, November 5, 2016

### LeetCode OJ - Rotate List

Problem:

Solution:

To rotate this list 1 -> 2 -> 3 -> 4 -> 5 to become 4 -> 5 -> 1 -> 2 -> 3.

Three things need to happen.

5 points to 1
3 points to NULL.

Since we need to change 5, we will always need to walk the whole list, the performance is $O(n)$.

The only problem I have with this problem is the judge. It appears to me that the test case is wrong, not sure what I can do about that. I have already emailed their admin.

[1, 2, 3] rotate 20000000 times = [1, 2, 3] rotate two times should be [3,1,2], and my code does output that correctly.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/rotate-list/

#include "LEET_ROTATE_LIST.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_ROTATE_LIST
{
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
{
int length = 0;
while (cur != nullptr)
{
cur = cur->next;
length++;
}
if (length == 0)
{
return nullptr;
}
k = k % length;
if (k == 0)
{
}
for (int i = 0; i < length - 1; i++)
{
cur = cur->next;
}
for (int i = 0; i < k - 1; i++)
{
cur = cur->next;
}
cur->next = nullptr;
}
};
};

using namespace _LEET_ROTATE_LIST;

int LEET_ROTATE_LIST()
{
Solution solution;
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
}