C语言经典例73-反向输出一个链表

女爷i 2023-07-06 11:40 64阅读 0赞

### 目录 ###

*  1 题目
 *  2 分析
 *   *  2.1 方法1-原地逆置
     *  2.2 方法2-递归
 *  3 实现
 *   *  3.1 实现1-原地逆置
     *  3.2 实现2-递归
 *  4 运行结果

# 1 题目 #

反向输出一个链表，链表结构为：

typedef int ElementType;
    typedef struct node { 
        ElementType data;
        struct node *Next;
    } *List;

# 2 分析 #

## 2.1 方法1-原地逆置 ##

原地逆置链表的思路是将原链表的头节点和其余节点分成两个部分，然后将其余节点逐个取下节点进行头插法插入到原链表的头结点前面，这样就实现了链表原地逆置，且空间复杂度为  O ( 1 ) O(1) O(1)。

List reverse(List L)
    { 
        List prep;
    	List p;
    	List q;
        p = L->Next;
        q = p->Next;
        p->Next = NULL;
        while (q) { 
            prep = p;
            p = q;
            q= q->Next;
            p->Next = prep;
        }
        L->Next = p;
        return L;
    }

## 2.2 方法2-递归 ##

上面的一种情况是强制改变链表原有顺序，那么也可以不改变链表的顺序，只逆序输出，那么可以使用递归，采用栈的思想，当链表的下一节点不为空`NULL`时进行递归，当链表的下一节点为`NULL`时返回递归输出节点数据，如下：

void reverse_2(List L) { 
    	if (L->Next != NULL) { 
    		reverse_2(L->Next);
    	}
    	printf("%d ", L->data);
    }

调用方法为：

reverse_2(L->Next);

# 3 实现 #

## 3.1 实现1-原地逆置 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    typedef int ElementType;
    typedef struct node { 
        ElementType data;
        struct node *Next;
    } *List;
    
    // 创建链表
    List CreateList(void) { 
        List L = (List)malloc(sizeof(struct node));
        L->data = 0;
        L->Next = NULL;
        return L;
    }
    
    // 初始化链表节点数据
    void InitList(List L) { 
        srand((unsigned)time(NULL)); // 随机数种子
        for (int i = 0; i < 10; i++) { 
            List p = (List)malloc(sizeof(struct node));
            p->data = rand() % 100; // 节点数据采用随机数，随机数范围为0~99
            p->Next = L->Next;
            L->Next = p;
        }
    }
    
    // 打印链表
    void PrtList(List L) { 
        List p = L->Next;
        while (p) { 
            printf("%d ", p->data);
            p = p->Next;
        }
        printf("\n");
    }
    
    // 逆置链表 
    List reverse(List L)
    { 
        List prep;
    	List p;
    	List q;
        p = L->Next;
        q = p->Next;
        p->Next = NULL;
        while (q) { 
            prep = p;
            p = q;
            q= q->Next;
            p->Next = prep;
        }
        L->Next = p;
        return L;
    }
    
    int main(void) { 
        List L = CreateList(); // 创建链表
        InitList(L); // 初始化链表数据
    	printf("原链表为：");
        PrtList(L);
    	reverse(L); // 逆置链表
    	printf("逆置后为：");
        PrtList(L);
        return 0;
    }

## 3.2 实现2-递归 ##

见`2.2 方法2-递归`中的程序段。

# 4 运行结果 #

原链表为：50 6 12 12 55 60 57 47 85 29
    逆置后为：29 85 47 57 60 55 12 12 6 50