單鏈表逆序操作

//逆序操作
//算法1：從第二個節點開始，記錄它的下一個節點，然后依次挪到第一個節點之前成為新表頭
int inverse_node(struct node pH)
{
struct node p = pH; //頭結點
struct node pPrev = NULL; //記錄前一個節點
struct node pBack = NULL; //記錄下一個節點地址
struct node *pFirstNode = p->pNext; //記錄第一個節點

//節點只有1個或者無有效節點時，返回原來的鏈表，不用進行逆序操作
if((NULL == pFirstNode) | (NULL == pFirstNode->pNext))  
{
    return 0;
}
//節點數兩個或以上時
else
{   
    p = p->pNext;           //節點1   
    pBack = p->pNext;       //節點2
    pPrev = p;              //節點1
    p = pBack;              //節點2

    while(NULL != p->pNext)
    {
        pBack = p->pNext;   //節點3
        pH->pNext = p;
        p->pNext = pPrev;
        pPrev = p;
        p = pBack;
    }   
}

pH->pNext = p;
p->pNext = pPrev;

pFirstNode->pNext = NULL;

return 0;

}
運行結果：

整體代碼：

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

//單鏈表的節點模型。
struct node
{
int data;
struct node *pNext;
};

//創建一個節點。
//有效數據為data。
//返回一個指針，該指針指向struct node類型，即創建的節點。
struct node create_node(int data)
{
//malloc申請一段內存來存儲數據
struct node p = (struct node *)malloc(sizeof(struct node));

//檢驗是否申請內存成功
if(NULL == p)
{
    printf("malloc error.\n");
    return NULL;
}

p->data = data;
p->pNext = NULL;

return p;

}

//從尾部插入一個新的節點new,pH為頭節點
void insert_tail(struct node pH, struct node new)
{
struct node *p = pH;

//讓p指向最后一個節點
while(NULL != p->pNext)
{
    p = p->pNext;
}

p->pNext = new;

}

//從頭部插入一個新的節點，pH為頭節點，new為新插入節點
void insert_head(struct node pH, struct node new)
{
struct node *p = pH;

if(NULL == p->pNext)
{
    p->pNext = new;
}
else
{
    new->pNext = p->pNext;
    p->pNext = new;
}

}

//遍歷節點
void ergodic(struct node pH)
{
struct node p = pH;

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

}

//刪除存儲數據為data的節點
void delete_node(struct node pH, int data)
{
struct node p = pH;
struct node *pPrev = NULL;

while(NULL != p->pNext)
{
    pPrev = p;                      //這個指針用來存儲上一個節點的地址
    p = p->pNext;                   //p指向下一個節點

    //找到要刪除的節點
    if(p->data == data)
    {
        //這個節點是尾節點
        if(NULL == p->pNext)
        {
            pPrev->pNext = NULL;
        }
        //不是尾節點
        else
        {
            pPrev->pNext = p->pNext;
        }

        free(p);                    //刪除節點，釋放節點的存儲空間
    }
}

}

//逆序操作
//算法1：從第二個節點開始，記錄它的下一個節點，然后依次挪到第一個節點之前成為新表頭
int inverse_node(struct node pH)
{
struct node p = pH; //頭結點
struct node pPrev = NULL; //記錄前一個節點
struct node pBack = NULL; //記錄下一個節點地址
struct node *pFirstNode = p->pNext; //記錄第一個節點

//節點只有1個或者無有效節點時，返回原來的鏈表，不用進行逆序操作
if((NULL == pFirstNode) | (NULL == pFirstNode->pNext))  
{
    return 0;
}
//節點數兩個或以上時
else
{   
    p = p->pNext;           //節點1   
    pBack = p->pNext;       //節點2
    pPrev = p;              //節點1
    p = pBack;              //節點2

    while(NULL != p->pNext)
    {
        pBack = p->pNext;   //節點3
        pH->pNext = p;
        p->pNext = pPrev;
        pPrev = p;
        p = pBack;
    }   
}

pH->pNext = p;
p->pNext = pPrev;

pFirstNode->pNext = NULL;

return 0;

}

int main(void)
{
//頭指針指向頭結點
struct node pHead = NULL;
pHead = create_node(0);
//struct node pHead = create_node(0);

insert_tail(pHead, create_node(11));
insert_tail(pHead, create_node(12));
insert_tail(pHead, create_node(13));
insert_tail(pHead, create_node(14));
insert_tail(pHead, create_node(15));
insert_tail(pHead, create_node(16));
insert_tail(pHead, create_node(17));

ergodic(pHead);

inverse_node(pHead);

printf("------------逆序后------------\n");

ergodic(pHead);

/
pHead->pNext = create_node(11);
pHead->pNext->pNext = create_node(12);
pHead->pNext->pNext->pNext = create_node(13);
/
/
printf("node1 data : %d\n",pHead->pNext->data);
printf("node2 data : %d\n",pHead->pNext->pNext->data);
printf("node3 data : %d\n",pHead->pNext->pNext->pNext->data);
/
return 0;
}