辞不达意

给定一单链表的表头指针和指向其中一个节点的指针，要求以该指针为头将原链表逆序排列，例如：

N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N3，返回N3->N2->N1->N5->N4->NULL
N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N5，返回这个N5->N4->N3->N2->N1->NULL
N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N1，返回这个N1->N5->N4->N3->N2->NULL
不允许额外分配存储空间，不允许递归，可以使用临时变量。

没有去管 malloc() 的返回值，也没有管 free() 的问题，但是考虑了 pSTART 是空指针的问题。数据类型仅用了一个 char 来演示。NULL 用 0 写了，省事。逆序的思路是先把链表接成循环的，然后从 pStart 处开始前插。

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

typedef struct link_st {
    char c;
    struct link_st *link;
} link_t;

link_t * new_node(char c)
{
    link_t * node = malloc(sizeof(link_t));
    node->c = c;
    node->link = 0;
    return node;
}

void print_link(const link_t * link)
{
    while (link != 0) {
        printf("%c ", link->c);
        link = link->link;
    }
    printf("$\n");
}

link_t * reverse(link_t **head, link_t *start)
{
    link_t *p, *q, *save;

    /* make it be a circle link */
    p = start != 0 ? start : *head;
    while (p->link != 0)
        p = p->link;
    p->link = *head;

    /* reverse, preinsert */
    if (0 == start)
        start = p;
    save = p = start->link;
    while (p != start) {
        q = p->link;
        p->link = start->link;
        start->link = p;
        p = q;
    }

    /* break the circle */
    save->link = 0;

    *head = start;
    return *head;
}

int main()
{
    int i;
    link_t *h, *nhead;

    h = new_node('A');
    h->link = new_node('B');
    h->link->link = new_node('C');
    h->link->link->link = new_node('D');
    h->link->link->link->link = new_node('E');
   
    print_link(h);
    nhead = reverse(&h, h->link->link->link);
    print_link(h);

    nhead = reverse(&h, 0);
    print_link(h);

    return 0;
}

运行结果：

wayman ~/t $ gcc -o link link.c
wayman ~/t $ ./link
A B C D E $
D C B A E $
E A B C D $