有一個線性表，採用帶頭結點的單鏈表L來存儲，設計一個演算法將其逆置，且不能建立新節點，只能通過表中已有的節點的重新組合來完成。

分析:線性表中關於逆序的問題,就是用建立鏈表的頭插法.而本題要求不能建立新結點,也就不能把元素重新弄到一個表中.可以將L中的元素作為逆轉後的L的元素來源,將L->next設置為空.然後將頭結點後的一串結點用頭插法逐個插入L中.

偽代碼:

void reversel(LNode *L)
{
    LNode *p=L->next, *q;
    L->next=NULL;            //置為空
    while(p!=NULL)
    {
        q=p->next;           //q記錄p的直接後繼結點的位置
        p->next=L->next;
        L->next=p;
        p=q;
    }
}

cue:

1.LNode *p, *q;

並不是建立新結點,它們只是存儲地址的變數.(我第一次遇到這個問題時沒弄懂,以為這兩是定義了新的結點.其實不是.)

2LNode *A=(LNode*)malloc(sizeof(LNode));

才是用戶分配了一片LNode型空間,也就是構造了一個LNode型結點.這時候定義了名為A的指針來指向這個結點,同時我們也把A也當做這個結點的名字.這裡A命名了兩個東西,一個是結點,一個是指向這個結點的指針.

指針變數自身的存儲空間是系統分配的,不需要用戶調用函數free()釋放,只有用戶分配的存儲空間才需要用戶自己來釋放.