请详细解释如何分别利用顺序表和单链表的数据结构，来实现一个操作，即将线性表（a0, a1, ..., an-1）在不使用额外辅助空间（空间复杂度为O(1)）的情况下进行就地递置？用C语言实现该数据结构题目

在不使用额外辅助空间的情况下，将线性表进行就地递置意味着我们需要交换每个元素与其前一个元素的位置。对于顺序表（数组），我们可以通过简单的指针移动和元素值交换来实现；而对于单链表，由于节点间的连接不是通过索引来建立的，我们需要修改每个节点的next指针。

**顺序表（数组）实现：**

void rotateArrayInPlace(int arr[], int n, int k) {
    if (n <= 1 || k == 0)
        return;

    // 将k取模，处理k > n的情况
    k = k % n;
    
    for (int i = 0; i < n - k; ++i) {
        // 临时保存arr[i]的值
        int temp = arr[i];
        
        // 移动元素到新的位置
        arr[i] = arr[n - k + i]; // arr[i] <- arr[k+i]
        
        // 将原arr[k+i]移动到arr[i]的位置
        arr[n - k + i] = temp;
    }
}

**单链表实现（假设链表节点结构为`struct Node`）：**

void rotateLinkedList(struct Node* head, int k) {
    if (head == NULL || k <= 0)
        return;

    // 计算链表的实际长度
    int len = 1, current = head;
    while (current->next != NULL) {
        current = current->next;
        len++;
    }

    // 将k取模，处理k > len的情况
    k %= len;

    // 如果k是0，直接返回，无需旋转
    if (k == 0)
        return;

    // 找到新头结点
    current = head;
    for (int i = len - k; i > 0; i--)
        current = current->next;

    // 将新头结点指向旧头结点的下一个节点
    current->next = head;
    // 新头结点成为新的头结点
    head = current->next;
}

**相关问题--:**
1. 这两种方法的时间复杂度分别是多少？
2. 在顺序表中为什么可以直接交换元素而不需要考虑内存布局？
3. 单链表的实现为何需要计算链表实际长度？