61. 旋转链表

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

1
2
3
4
示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
1
2
3
4
示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]
1
2
3
4
提示：
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

题解

本题不难，只需要找到newHead和newTail的位置，将原来的tail和原来的head连接，返回newHead就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* rotateRight(struct ListNode* head, int k){
    if (head == NULL) return NULL;  // Exception: empty list
    struct ListNode* preHead = head;
    struct ListNode* newHead = head;
    struct ListNode* newTail = head;
    struct ListNode* preTail = head;
    int ListSize = 1;
    // get the total size of the list as well as the previous tail of the list
    for (; preTail->next != NULL; preTail = preTail->next, ListSize++);
    k %= ListSize;
    if (k == 0) return head;
    // get the new tail of the new list
    // new head of the list is the successor of the new tail
    for (int i = 0; i < ListSize - k - 1; i++, newTail = newTail->next);
    newHead = newTail->next;
    newTail->next = NULL;
    // connect the previous tail to the previous head;
    preTail->next = preHead;
    return newHead;
}