关于c:旋转链表

61次阅读

共计 753 个字符,预计需要花费 2 分钟才能阅读完成。

给你一个链表的头节点 head,旋转链表,将链表每个节点向右挪动 k 个地位。

示例 1:


输出:head = [1,2,3,4,5], k = 2
输入:[4,5,1,2,3]

示例 2:


输出:head = [0,1,2], k = 4
输入:[2,0,1]

提醒:
链表中节点的数目在范畴 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

思路:
将 k 对链表长度 (后记为 len) 取模,如果 k 与 len 相等, 则 k = len, 再进行旋转(余数为多少就旋转多少次)。

获取链表长度(帮忙函数):

int length(struct ListNode* p) {
    struct ListNode* q = p;
    int length = 0;

    while (q != NULL) {
        length++;
        q = q->next;
    }

    return length;
}

单次旋转:

void rotate(struct ListNode **p) {
    struct ListNode* q = *p;
    struct ListNode *secondToLast = *p;

    while (q != NULL) {if (q->next != NULL) {secondToLast = q;}
        q = q->next;
    }

    secondToLast->next->next = *p;
    *p = secondToLast->next;
    secondToLast->next = NULL;
}
struct ListNode* rotateRight(struct ListNode* head, int k) {int len = length(head);
    if (len == 0 || len == 1) return head;
    int _k;
    if (k % len == 0) {_k = len;}
    else {_k = k % len;}

    for (int i = 0; i < _k; i++) {rotate(&head);
    }

    return head;
}

正文完
 0