单链表逆置算法详解

思路：

首先创建一个单链表，返回一个头节点的指针（ head 该头节点不为 NULL,
其次进行单链表的逆置设置。具体设置方法见下：

1.单链表的原有示意图

image.png

2.断开 head 和 R 之间链接 使 head 指向 NULL

image.png

3.使 R 指向 head

image.png

4.断开 R 和 Q 之间的链接

image.png

5.使 Q 指向 R

image.png

6.最后的结果是：

image.png

根据不同的长度依次进行逆置

源码如下：

#include<stdio.h>
#include<stdlib.h>
Typedef struct List
{
    int num;
    struct List *next;
}LNode, LinkList;
/*****************************************
*Funtion: LNode*Creation(int n)
*Descrition: create a singly linked list according to the specified length
*Param: n indicate the length you want to create.
*Data:2014-02-28
*****************************************/
LNode *Creation(int n)
{
    LinkList head; //定义一个头节点
    LinkList p1; //定义中间转换的节点
    LinkList p2;
    Head = NULL； //初始化头节点
        int num;
    int i;
    for (i = n; i > 0; --i)
    {
        p1 = (LinkList)malloc(sizeof(LNode)); //分配内存
        scanf(“%d”, &num);
        p1->num = num;
        if (head == NULL)
        {
            head = p1;
        }
        else
        {
            p2->next = p1; //指定后继节点
        }
        p2 = p1; //节点后移
    }
    p2->next = NULL;
    return head;
}
/*******************************
*Function: LinkList Reverse(LNode *head)
*Descrition: reverse the link according to head;
*Data:2014-02-28
******************************/
LinkList Reverse(LNode *head)
{
    LNode *p; //定义中间转换节点
    LNode *r;
    if (head->next && head->next->next)
    {
        p = head; //获取头节点地址
        r = p->next; //获取链表第二个节点地址
        p->next = NULL; //头节点变尾节点之后下个指向是NULL
        while (r)
        {
            p = r; //第一个节点顺移
            r = r->next; //第二个节点顺移
            p->next = head; // 使第二个节点的下一个节点指向前一个
            head = p; //给头节点赋值
        }
        return head;
    }
    return head;
}
//the entry function
int main()
{
    LinkList p1;
    LinkList p2;
    int num;
    printf(“输入你想创建的链表长度\n”);
    scanf(“%d”, &num);
    printf(“创建一个单向链表\n”);
    p1 = Creation(num);
    printf(“逆置链表\n”);
    p2 = Reverse(p1);
    printf(“逆置之后的链表是:”)
        while (p2)
        {
            printf(“%d ”, p2->num);
            p2 = p2->num;
        }
    return 0;
}