单链表逆置与顺序表逆置的实现

单链表逆置

思想

将给定的单链表就地逆置，可以通过以下方法实现：首先，将链表的头节点的下一个节点保存到一个临时指针p，并使链表的头节点L的下一个指针为null。然后，利用头插法，将原链表的后续节点依次插入到头部，形成逆序的链表。

代码

Status T222(LinkList L) {
    LinkList pre, p;
    if (!L || !L->next) {
        return ERROR; // 链表为空或只有一个节点
    }
    p = L->next;
    L->next = NULL; // 头节点的下一个指针置为空
    while (p) {
        // 头插法
        pre = p;
        p = p->next;
        pre->next = L->next;
        L->next = pre;
    }
    return OK;
}

顺序表逆置

思想

对顺序表的逆置可以通过两两交换的方式实现：从两端向中间交换元素，直到中间位置。具体来说，第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换，以此类推，直到中间位置。

代码

Status T221(SeqList L) {
    int i, j;
    ElemType tmp;
    if (L->length == 0) {
        return ERROR; // 空表
    }
    for (i = 1, j = L->length / 2; j <= i; j++) {
        tmp = L->elem[j - 1];
        L->elem[j - 1] = L->elem[L->length - j];
        L->elem[L->length - j] = tmp;
    }
    return OK;
}

以上代码均为C语言实现，适用于上述两种数据结构的逆置操作。通过这种方法，可以在原地对单链表和顺序表进行逆置操作，节省空间资源。

转载地址：http://kutwz.baihongyu.com/

你可能感兴趣的文章