欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表逆置代码解析

程序员文章站 2024-01-15 15:43:46
...
#include <stdio.h>
#include <malloc.h>
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*Linklist;
Linklist Insertlist_last(Linklist head)//尾插
{
    Linklist p;
    Linklist q;
    int i;
    head=(Linklist)malloc(sizeof(LNode));
    head->next=NULL;
    q=head;
    scanf("%d",&i);
    while(i!=0)
    {
        p=(Linklist)malloc(sizeof(LNode));
        //scanf("%d",&p->data);
        p->data=i;
        q->next=p;
        q=p;
        scanf("%d",&i);
    }
    q->next=NULL;
    return head;
}


Linklist change(Linklist head)//逆置算法
{
    Linklist p,q;
    p = head->next;    //P指向链表第一个元素
    head->next = NULL; //断开头结点与链表
    while(p != NULL)
    {
        q = p;
        p = p->next;
        q->next = head->next;  //相当于头插法构建新的链表
        head->next = q;//每下一个结点始终在第一个位置
    }
    return head;
}

int main()
{
    Linklist head,star;
    int get;
    head=Insertlist_last(head);
    head=change(head);
    star=head->next;
    while(star)
    {
        printf("%d  ",star->data);
        star=star->next;
    }
    return 0;
}

关键代码解析

q = p;
p = p->next;
q->next = head->next; //相当于头插法构建新的链表
head->next = q;//每下一个结点始终在第一个位置

q可以理解成一个中间变量,对p和head进行帮助的一个变量。p则是遍历链表的变量,p赋值给q后,p就会指向下一个结点,是循环遍历。(q = p;
p = p->next;)


q->next = head->next;这句可以理解成类似于头插法中将q指向的结点插入到head->next中的将head->next断开,使q进去(即插入新结点)

单链表逆置代码解析


head->next = q;上面语句操作后,就断开了之前的,然后就是正式将head->next指向q结点了。这样就完成了每次遍历的一个结点都会放在最前面,即完成了逆置

相关标签: 单链表 逆置