链表逆序

设链表节点为
typedef struct node {
    int data;
    struct node *next;
}node_t, *pnode_t;

要求将一带链表头List head的单向链表逆序。

分析：

  1). 若链表为空或只有一个元素，则直接返回；

  2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继；

  3). 重复2),直到q为空

  4). 调整链表头和链表尾

示例：以逆序A->B->C->D为例，图示如下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 10

typedef struct node {
    int data;
    struct node *pnext;
} node_t, *pnode_t;

pnode_t create_link()
{
    int i;
    pnode_t phead;

    phead = (pnode_t)malloc(sizeof(node_t));
    if (phead == NULL) {
        printf("malloc fail.\n");
        exit(-1);
    }
    memset(phead, 0, sizeof(node_t));

    pnode_t ptail = phead;

    for (i = 0; i < LEN; i++) {
        pnode_t    pnew = (pnode_t)malloc(sizeof(node_t));
        if (pnew == NULL) {
            printf("malloc fail.\n");
            exit(-1);
        }
        memset(pnew, 0, sizeof(node_t));

        pnew->data = i+1;
        pnew->pnext = NULL;
        ptail->pnext = pnew;
        ptail = pnew;
    }

    return phead;
}

void print_link(pnode_t phead)
{
    pnode_t p = phead->pnext;

    while (p != NULL) {
        printf("%d ", p->data);
        p = p->pnext;
    }
    printf("\n");
}

void reverse_link(pnode_t phead)
{
    pnode_t p, q, ptmp;

    p = phead->pnext;
    q = phead->pnext->pnext;
    ptmp = NULL;

    while (q != NULL) {
        ptmp = q->pnext;
        q->pnext = p;
        p = q;
        q = ptmp;
    }

    phead->pnext->pnext = NULL;
    phead->pnext = p;
}

int main(int argc, char *argv[])
{
    pnode_t phead = NULL;

    phead = create_link();

    print_link(phead);

    reverse_link(phead);
    print_link(phead);

    return 0;
}