单链表的逆转

太过爱你忘了你带给我的痛 2022-06-01 08:43 133阅读 0赞

**方法1：**将单链表储存为数组，然后按照数组的索引逆序进行反转。

**方法2：**使用3个指针遍历单链表，逐个链接点进行反转。

**方法3：**从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

**方法4:** 递归

**方法1：**感觉多此一举，浪费空间

**方法2：**

使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。  
p = head;  
q = head->next;

![SouthEast][]

head->next =NULL;

![SouthEast 1][]

现在进入循环体，这是第一次循环。

r = q->next;

q->next= p;

![SouthEast 2][]

p = q;

q = r;

![SouthEast 3][]

第二次循环。

r = q->next

q->next = p;![SouthEast 4][]

![SouthEast 5][]

p = q；

q = r；![SouthEast 6][]

![SouthEast 7][]

第三次循环……

#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;
    }
    
    /* 你的代码将被嵌在这里 */
    List Read()
    {
        int n;
        scanf("%d",&n);
        List a=(List)malloc(sizeof(struct Node));
        List head=a;
        while(n--)
        {
            scanf("%d",&a->Data);
            if(n)
            {
                a->Next=(List)malloc(sizeof(struct Node));
                a=a->Next;
            }
        }
        a->Next=NULL;
        return head;
    }
    void Print( List L )
    {
        while(L)
        {
            printf("%d ",L->Data);
            L=L->Next;
            List Read()
            {
                int n;
                scanf("%d",&n);
                List a=(List)malloc(sizeof(struct Node));
                List head=a;
                while(n--)
                {
                    scanf("%d",&a->Data);
                    if(n)
                    {
                        a->Next=(List)malloc(sizeof(struct Node));
                        a=a->Next;
                    }
                }
                a->Next=NULL;
                return head;
            }
            void Print( List L )
            {
                while(L)
                {
                    printf("%d ",L->Data);
                    L=L->Next;
                }
                printf("\n");
            }
        }
        printf("\n");
    }
    
    
    List Reverse( List L )
    {
        List p,q,r;
    if(L == NULL || L->Next == NULL)
        return L;
        p=L;
        q=p->Next;
    
        r=NULL;
        L->Next=NULL;
    
        while(q)
        {
            r=q->Next;
            q->Next=p;
            p=q;
            q=r;
    
        }
        L=p;
        return L;
    
    }

[SouthEast]: /images/20220601/4d7f6f223d9b47b591a1d0e9622238da.png
[SouthEast 1]: /images/20220601/433d1e410684428f83ef84b4dd6fb4de.png
[SouthEast 2]: /images/20220601/e2804133cb1944ecb04ebb5a5bfdeb41.png
[SouthEast 3]: /images/20220601/630c294294c24d55bbf25beb90b73ab9.png
[SouthEast 4]: /images/20220601/be23b032961b422290fa37fdfd11f4e3.png
[SouthEast 5]: /images/20220601/c82887a8c7744c4d87e6858c6a1e5070.png
[SouthEast 6]: /images/20220601/9115b5b668e647839ca0d8f886c31d2c.png
[SouthEast 7]: /images/20220601/05763782c1564580874ea6a83d6d9882.png