帶頭結點的連結清單的逆置

版權聲明：本文為部落客原創文章，轉載請注明出處。 https://blog.csdn.net/twilight_karl/article/details/53074257

不需要申請新的記憶體，在原有的連結清單的基礎上實作逆置連結清單

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

typedef struct link{
    char data;
    struct link * next;
}LinkList;

LinkList * setList();               //初始化連結清單
void initList(LinkList * );         //初始化連結清單，給連結清單指派
void show(LinkList * );             //輸出所有元素
void Reverse(LinkList * L);         //逆置連結清單

int main (){
    LinkList * head = setList();
        initList(head);
        show(head);
        Reverse(head);
        show(head);
        system("pause");
    return 0;
}

LinkList * setList (){
    LinkList * head = (LinkList *)malloc(sizeof(LinkList));
    head ->next = NULL;
    return head ;
}

void initList (LinkList * s ){
    char ch ;
    LinkList * p = s;
    printf("輸入元素: （#号結束） \n");
    while((ch = getchar()) != '#'){
        fflush(stdin);
        LinkList * temp = (LinkList *)malloc(sizeof(LinkList));
        temp ->data  = ch ;
        temp ->next  = p ->next ;
        p ->next = temp;
        p = p->next;
    }
}

void show (LinkList * s){
    LinkList * p = s ->next ;
    printf("\n連結清單中的元素有: ");
    while(p != NULL){
        printf("%c ",p->data );
        p = p->next ;
    }
    putchar ('\n');
}
void Reverse(LinkList * L)
{
 LinkList * p ;
 LinkList * q ;
 p = L->next ;
 q = p;
 L->next = NULL;        //斷開頭結點

 while (p!= NULL){
    q = p -> next ;     //擷取p的下一個節點的位址
    p->next = L->next;  //将p節點插入到頭結點L後面，p的後記節點指向L原有的節點
    L->next = p ;       //p為頭結點的第一個元素，頭結點的後記節點指向p
    p = q ;             //p指向下一個需要交換的節點
 }
}