单链表逆转（Reversing Linked List）

冷不防 2023-07-03 08:23 3阅读 0赞

输入数据：  
给定头结点的地址，以及接下来的结点个数N，和要逆转的结点个数K，接下来输入N组数据，分别是一个结点的地址，以及其元素，和其指针。（输入的结点不一定在同一条链表上)。  
sample input：  
00100 6 4  
00000 4 99999  
00100 1 12309  
68237 6 -1  
33218 3 00000  
99999 5 68237  
12309 2 33218  
要求将前k个结点构成的链表逆转后输出。  
将其在内存中的状态写成表格的形式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]

在样例输入的情况下，将6个结点的前四个进行逆转：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]  
为了更简单的表示，可以在第一个结点之前增加一个头结点，在空间足够的情况下。我们需要先创建一个指针new，指向已经完成逆转的结点，初始位置放在1处，在创建一个指针old，指向当前还没有完成逆转的部分链表的头位置，初始状态在2处，接下来就可以把2的指针指向1了，但是在逆转2的指针之前，我们需要创建一个指针tmp，来指向3，否则调整了2的指针之后，就没有指向3的指针了，后面的部分就丢掉了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 2]  
完成了第一的操作后，继续循环执行，将new指针指向下一个结点2，将old指针移到下一个待逆转的结点3，tmp同样后移动，记住4的位置防止后序的丢失。一共执行k步后，完成了要求个数的逆转，当前链表的状态应当是下图的状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 3]  
此时1的指针还指着2，应当将1的指针指向还没有完成转换的链表的头位置处，也就是old指针当前的位置，即为5处；再将我们事先创建的头结点，指向完成逆转之后的链表头处，即为new指针的位置，4处。这样链表就完成了规定的逆转。  
伪代码如下：

Ptr reverse(Ptr head,int K)
    {
        
        cnt=1;//计数用
        new=head->next;//先将初始位置标记为1号
        old=new->next;
        while(cnt<K){
        
            tmp=old->next;//记录old的下一个
            old->next=new;//逆转指针
            new=old;
            old=tmp;
            cnt++;//向后移
        }
        head->next->next=old;//将1的指针指向5（样例中）
        return new;
    }

PTA原题：  
**6-1 单链表逆转（20 point(s)）  
本题要求实现一个函数，将给定的单链表逆转。  
函数接口定义：**

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

List reverse(List head)
    {
        
        List new,old,tmp;
        new=head->Next;
        old=new->Next;
        while(old!=NULL){
        
            tmp=old->Next;
            old->Next=new;
            new=old;
            old=tmp;
        }
        return head;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200205103850472.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200205104106183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200205131943409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200205133521873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70