链表就地逆置

笔者对于这个链表的就地逆置算法感觉比较绕！今天就彻底的消灭了他。现将总结如下。

就地逆置，就是在不借助任何中间变量的情况下，逆置一单链表。

算法思路：

      逆置后的点链表初始为空，表中的节点不是新生成的，而是从原链表当中一次“删除”，再逐个头插到逆置表中。设逆置链表的初始态为空表，“删除”已知链表中的第一个节点，然后将它“插入”到逆置链表的“表头”，即使得他成为逆置链表中“新”的第一个节点，如此循环，直至原链表为空。

假设有如下数据结构：

#define ElemType char

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node,*LinkList;

如下图所示：

代码如下：

void ReverseList(LinkList L)
{
    Node *p,*q;
    p = L->next;             /*p为原链表的当前处理节点*/
    L->next = NULL;          /*逆置单链表初始为空*/

    while(p != NULL){        /*当原链表未处理完*/
        q = p->next;         /*q指针保留原链表当前处理节点的下一个节点*/
        p->next = L->next;   /*将当前处理节点p插入到逆置L的表头*/
        L->next = p;
        p = q;               /*p指向下一个待插入的节点*/
    }
}

其实也比较简单；就是有点绕。

同时给出头插法建立链表的代码：

void CreatList(LinkList L)
{
    Node *s;
    char c;
    int flag = 1;
    while(flag){
        c = getchar();
        if(c != '$'){
            s = (Node*)malloc(sizeof(Node));
            s->data = c;
            s->next = L->next;
            L->next = s;
        }else
            flag = 0;
    }
}

其实这仅仅是两个部分，现在给出笔者再ubuntu下的运行结果：

下载代码： ReverseList.txt