C语言数据结构旋转链表的实现

C语言数据结构旋转链表的实现

1. 什么是旋转链表

旋转链表是一种特殊的链表，其特点是将链表的最后一个节点移动到最前面，形成一个环形链表的效果。比如下面这个链表：

1 -> 2 -> 3 -> 4 -> 5

经过一次旋转之后变成了：

5 -> 1 -> 2 -> 3 -> 4

2. 实现思路

旋转链表的实现思路比较简单，主要可以分为以下几步：

1. 找到链表最后一个节点，并将其与头节点相连，形成一个环形链表。
2. 找到新的链表尾节点（旋转后的头节点），断开环形链表，形成新的链表。

3. 实现代码

下面是旋转链表的C语言实现代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* rotateRight(struct ListNode* head, int k) {
    struct ListNode *p, *q;
    int len = 0;
    p = q = head;

    // 计算链表长度
    while (p) {
        len++;
        p = p->next;
    }

    // 链表为空或长度为1，直接返回原链表
    if (len == 0 || len == 1) {
        return head;
    }

    // 计算旋转后的头节点位置
    k = k % len;
    if (k == 0) {
        return head;
    }

    // 找到旋转后的头节点和尾节点
    for (int i = 1; i <= k; i++) {
        q = q->next;
    }
    p = head;
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
    }

    // 断开环形链表，形成新的链表
    q->next = head;
    head = p->next;
    p->next = NULL;
    return head;
}

4. 示例说明

示例一：

给定链表: 1->2->3->4->5->NULL，k = 2
旋转后的链表: 4->5->1->2->3->NULL

示例二：

给定链表: 0->1->2->NULL，k = 4
旋转后的链表: 2->0->1->NULL