c语言如何原地倒置链表

链表的原地倒置是指不使用额外的空间，直接在原链表上进行操作，将链表中的节点顺序翻转。具体实现方法如下：

/* 原地倒置链表 */
void reverseList(LinkNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    LinkNode *p = head->next, *q = p->next;
    head->next = NULL;
    while (q != NULL) {
        p->next = head->next;
        head->next = p;
        p = q;
        q = q->next;
    }
    p->next = head->next;
    head->next = p;
}

该方法的时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

c语言创建有序链表

好的，以下是用C语言创建一个有序链表的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode* next;
};

// 插入元素到有序链表中
struct ListNode* insert(struct ListNode* head, int val) {
    // 创建新节点
    struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
    new_node->val = val;
    new_node->next = NULL;
    
    if (head == NULL) {
        // 如果链表为空，则直接插入新节点
        head = new_node;
    } else if (head->val > val) {
        // 如果新节点的值小于链表头结点的值，则将新节点作为新的头结点
        new_node->next = head;
        head = new_node;
    } else {
        // 遍历链表，找到合适的插入位置
        struct ListNode* cur = head;
        while (cur->next && cur->next->val < val) {
            cur = cur->next;
        }
        new_node->next = cur->next;
        cur->next = new_node;
    }
    
    return head;
}

// 打印链表
void print_list(struct ListNode* head) {
    struct ListNode* cur = head;
    while (cur) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    struct ListNode* head = NULL;
    
    // 插入元素到有序链表中
    head = insert(head, 5);
    head = insert(head, 3);
    head = insert(head, 7);
    head = insert(head, 1);
    head = insert(head, 9);
    
    // 打印有序链表
    print_list(head);
    
    return 0;
}

这个示例代码中，我们定义了一个链表节点结构体 `ListNode`，包含了一个 `val` 域和一个指向下一个节点的指针 `next`。然后实现了一个 `insert` 函数，用于将一个新的元素插入到有序链表中。当链表为空时，直接插入新节点；当新节点的值小于链表头结点的值时，将新节点作为新的头结点；否则，遍历链表找到合适的插入位置。最后，我们用 `print_list` 函数打印出整个有序链表。

c语言双向循环链表例题

以下是一个C语言的双向循环链表的例题：

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (*head == NULL) {
        newNode->next = newNode;
        newNode->prev = newNode;
        *head = newNode;
    } else {
        struct Node* tail = (*head)->prev;

        newNode->next = *head;
        (*head)->prev = newNode;

        newNode->prev = tail;
        tail->next = newNode;
    }
}

void display(struct Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* current = head;

    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);

    printf("\n");
}

int main() {
    struct Node* head = NULL;

    // 插入节点
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);

    // 显示链表
    display(head);

    return 0;
}

这个例题演示了如何创建并打印一个双向循环链表。首先，我们创建了一个结构体 `Node`，其中包含数据 `data`、下一个节点指针 `next` 和前一个节点指针 `prev`。然后，我们定义了一个插入函数 `insert`，用于将新节点插入到链表中。最后，我们定义了一个显示函数 `display`，用于打印链表中的所有节点。在 `main` 函数中，我们创建一个空链表，然后插入了三个节点，并使用 `display` 函数打印链表的内容。

这个例题只是对双向循环链表的基本操作进行了演示，你可以根据需要修改和扩展这个代码来实现更复杂的功能。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [链表图解（双向、循环链表+链表增删）](https://blog.csdn.net/qq_52189899/article/details/121552785)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]