c - 在c中交换反转链表

Question

给定一个列表，我想通过交换第一个与最后一个、第二个与倒数第二个等交换来反转列表。

我编写了这个函数来交换每一对，其中 pos1 和 pos2 是要交换的两个位置。

maxPos 是两个位置中最大的，node1和node2是遍历列表后找到的两个节点。

int swap(struct node *list, int pos1, int pos2) {

    if (node1 != NULL && node2 != NULL) {
        if (prev1 != NULL)
            prev1->next = node2;
        if (prev2 != NULL)
            prev2->next = node1;
        temp        = node1->next;
        node1->next = node2->next;
        node2->next = temp;
        if (prev1 == NULL)
            head = node2;
        else if (prev2 == NULL)
            head = node1;
    }
    return 1;
}

而不是为每对递归地调用它，即。必须遍历的 (1,n-1)、(2,n-2)、(3,n-3)每次都会列出这个列表，我想知道是否有一种方法可以迭代解决它。

Answer 1

你真的想交换节点内容吗？

您可以使用一个非常简单的函数迭代地反转列表:

struct node {
    // whatever payload fields...
    struct node *next;
};

struct node *reverse_list(struct node *list) {
    struct node *last = NULL;
    while (list != NULL) {
        struct node *next = list->next;
        list->next = last;
        last = list;
        list = next;
    }
    return last;
}