PTA 6-1 单链表逆转 (20分) 三种解法

迈不过友情╰ 2023-01-03 14:28 132阅读 0赞

本题要求实现一个函数，将给定的单链表逆转。

### 函数接口定义： ###

List Reverse( List L );

其中`List`结构定义如下：

typedef struct Node *PtrToNode;
    struct Node {
        
        ElementType Data; /* 存储结点数据 */
        PtrToNode   Next; /* 指向下一个结点的指针 */
    };
    typedef PtrToNode List; /* 定义单链表类型 */

`L`是给定单链表，函数`Reverse`要返回被逆转后的链表。

### 裁判测试程序样例： ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        
        ElementType Data;
        PtrToNode   Next;
    };
    typedef PtrToNode List;
    
    List Read(); /* 细节在此不表 */
    void Print( List L ); /* 细节在此不表 */
    
    List Reverse( List L );
    
    int main()
    {
        
        List L1, L2;
        L1 = Read();
        L2 = Reverse(L1);
        Print(L1);
        Print(L2);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

### 输入样例： ###

5
    1 3 4 5 2

### 输出样例： ###

1
    2 5 4 3 1

# 分析题目 #

反转单链表，有三种思路，一种是`利用栈`，比较容易想，输出时尾插法即可，二是`迭代法`,遍历时从前往后，头插法，三是使用`递归`。

### 栈 ###

使用栈输出一下即时反转后的链表。这道题使用栈时，只能自己写一个数组栈模拟一下，没办法直接使用stack类。代码如下:

List Reverse( List L ){
        
    	List list[6],front,rear,temp;
    	int i = -1;
    	while(L!=NULL){
        
    		list[++i] = L;
    		L = L->Next;
    	}
    	if(i == -1){
        
    		return NULL;
    	}
    	front = list[i--];
    	rear = front;
    	while(i>=0){
        
    		temp = list[i--];
    		rear->Next = temp;
    		rear = rear->Next;
    	} 
    	rear->Next=NULL;
    	return  front;
    }

### 迭代法：对当前的节点使用头插法。 ###

图解：  
![在这里插入图片描述][20210108220131274.png_pic_center]  
![在这里插入图片描述][20210108220141548.png_pic_center]  
![在这里插入图片描述][20210108220149457.png_pic_center]  
![在这里插入图片描述][20210108220155555.png_pic_center]  
![在这里插入图片描述][20210108220200786.png_pic_center]

代码：

List Reverse( List L ){
        
        List head = NULL;
        while(L != NULL){
        
            List temp = L->Next;
            L->Next = head;
            head = L;
            L = temp ;
        }
        return head;
    }

### 递归 ###

递归写法需要将其看成两部分对待，每部分当成一个结点，一部分是反转好的链表，一部分时未反转的节点。

图解：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

代码：

List Reverse( List L ){
        
    	if(L== NULL || L->Next == NULL){
        
    		return L;
    	} 
    	List node = Reverse(L->Next);
    	L->Next->Next = L;
    	L->Next = NULL;
    	return node;
    }

[20210108220131274.png_pic_center]: /images/20221119/066281e88d8e47ef992ece6128e1a07c.png
[20210108220141548.png_pic_center]: https://img-blog.csdnimg.cn/20210108220141548.png#pic_center
[20210108220149457.png_pic_center]: https://img-blog.csdnimg.cn/20210108220149457.png#pic_center
[20210108220155555.png_pic_center]: https://img-blog.csdnimg.cn/20210108220155555.png#pic_center
[20210108220200786.png_pic_center]: https://img-blog.csdnimg.cn/20210108220200786.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210108220244911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70#pic_center