给定一个单链表，旋转链表，将链表每个节点向后移动 k 个位置，
如果是尾节点，则把它移动到最前面；其中 k 是正数。
要求：时间复杂度O(n)，空间复杂度O(1)
例如：
输入: 1->2->3->4->5->NULL, k = 1 输出: 5->1->2->3->4->NULL
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL
输入: 1->2->3->4->5->NULL, k = 3 输出: 3->4->5->1->2->NULL
输入: 1->2->3->4->5->NULL, k = 6 输出: 5->1->2->3->4->NULL
typedef struct node {
int value;
struct node *next;
} LinkNode;
// 创建链表
- (void)creatLinkList
{
LinkNode *trail = NULL;
LinkNode *head = NULL;
// 创建单向链表
for (int i = 0; i < 7; i++) {
LinkNode *newNode = malloc(sizeof(LinkNode));
newNode->value = i+1;
newNode->next = NULL;
if (!head) {
trail = newNode;
head = newNode;
}
trail->next = newNode;
trail = newNode;
}
LinkNode *p = reverList(head, trail, 7, 8);
while(p != NULL) {
printf("\t %d", p->value);
p = p->next;
}
}
LinkNode *reverList(LinkNode *head, LinkNode *trail, int lengh, int k)
{
if (k > lengh) k %= lengh;
if (k % lengh == 0) return head;
LinkNode *newTrail = NULL, *p = head;
LinkNode *newHead = p;
int newHeadIndex = lengh - k;
while (p && p->value <= newHeadIndex) {
newTrail = p;
newHead = p;
p = p->next;
}
newHead = newTrail->next;
trail->next = head;
newTrail->next = NULL;
return newHead;
}
另外思路：可以将原单链表转成循环链表，找到新的头尾指针，断开为指针，返回头指针。其实跟上面的复杂度也一模一样，只是将代码trail->next = head;挪到if语句之后即可。
