C语言算法-解答两两交换链表中的节点问题的C语言实现

题目

给定一个链表，两两交换相邻的节点，并返回交换后的新链表。

引言

两两交换链表中的节点问题需要考虑链表的指针操作和节点交换的逻辑。我们可以使用迭代的方法或递归的方法来解决这个问题。解决这个问题需要对链表进行指针操作和节点交换。

算法思路

我们将使用迭代的方法来解决两两交换链表中的节点问题。

算法的步骤如下：

1. 创建一个虚拟头结点 dummy，并将其指向原链表的头结点。
2. 创建一个指针 prev，指向虚拟头结点。

3. 迭代遍历链表，每次处理两个相邻的节点：

   • 如果剩余节点数小于两个，不需要进行交换，直接退出循环。
   • 否则，定义指针 node1 指向当前节点，定义指针 node2 指向下一个节点。
   • 将 prev 的下一个节点指向 node2。
   • 将 node1 的下一个节点指向 node2 的下一个节点。
   • 将 node2 的下一个节点指向 node1。
   • 将 prev 指向 node1，完成交换。
4. 返回虚拟头结点的下一个节点，即交换后的新链表的头结点。

代码实现

下面是使用C语言实现的代码：

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

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;

    ListNode* prev = dummy;

    while (head != NULL && head->next != NULL) {
        ListNode* node1 = head;
        ListNode* node2 = head->next;

        prev->next = node2;
        node1->next = node2->next;
        node2->next = node1;

        prev = node1;
        head = node1->next;
    }

    ListNode* newHead = dummy->next;
    free(dummy);

    return newHead;
}

void printList(ListNode* head) {
    ListNode* current = head;

    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }

    printf("\n");
}

int main() {
    // 创建示例链表: 1 -> 2 -> 3 -> 4
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;

    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->val = 2;
    head->next = node1;

    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->val = 3;
    node1->next = node2;

    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->val = 4;
    node2->next = node3;
    node3->next = NULL;

    printf("Original List: ");
    printList(head);

    ListNode* result = swapPairs(head);

    printf("Swapped List: ");
    printList(result);

    // 释放内存
    while (result != NULL) {
        ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

算法分析

该算法只需要对链表进行一次遍历，并在指针操作过程中进行节点交换，所以时间复杂度为 O(n)，其中 n 是链表的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入:

Original List: 1 -> 2 -> 3 -> 4

示例输出:

Swapped List: 2 -> 1 -> 4 -> 3

总结

本文使用C语言实现了解答两两交换链表中的节点问题的代码。通过使用迭代的方法，我们能够交换链表中相邻的两个节点，得到交换后的新链表。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。