給定一個單鏈表由捎，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向后移動 k 個位置燕刻，
如果是尾節(jié)點只泼，則把它移動到最前面；其中 k 是正數(shù)酌儒。
要求：時間復(fù)雜度O(n)辜妓，空間復(fù)雜度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;
// 創(chuàng)建鏈表
- (void)creatLinkList
{
LinkNode *trail = NULL;
LinkNode *head = NULL;
// 創(chuàng)建單向鏈表
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;
}
另外思路：可以將原單鏈表轉(zhuǎn)成循環(huán)鏈表枯途，找到新的頭尾指針忌怎，斷開為指針，返回頭指針酪夷。其實跟上面的復(fù)雜度也一模一樣榴啸，只是將代碼trail->next = head;挪到if語句之后即可。
