196
單鏈表的若幹問題
（1）.試編寫算法將帶頭結點單鏈表就地逆置，所謂“就地”是指輔助空間為O(1)
【解析】
此問題有兩種解法。
a 把頭節點摘下來，然後用頭插法建鏈表就形成所謂的就地逆置
b 依次遍曆將指針反轉，不過最後一個節點需要注意一下
兩算法時間複雜度都是O(n)，空間都是O(1)
【算法】
第一種算法：
//就地反轉
int LinkListRerverse(LinkList *head){
LinkList *q,*p;
p = head->next;
head->next = NULL;
while(p != NULL){
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
return 0;
}
完整例子：
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
int data;
struct Node *next;
}LinkList;
//就地反轉
int LinkListRerverse(LinkList *head){
LinkList *q,*p;
p = head->next;
head->next = NULL;
while(p != NULL){
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
return 0;
}
//輸出數據
int LinkListPrintf(LinkList *head){
LinkList *p;
p = head;
while(p->next){
p = p->next;
printf("%d ",p->data);
}
printf("\n");
return 0;
}
//創建鏈表
int LinkListCreate(LinkList *head,int n){
LinkList *p,*newNode;
head->next = NULL;
p = head;
//輸入數據
for(int i = 0;i < n;i++){
//創建節點
newNode = (LinkList*)malloc(sizeof(LinkList));
scanf("%d",&newNode->data);
newNode->next = p->next;
p->next = newNode;
p = newNode;
}
return 0;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF){
LinkList *head;
head = (LinkList*)malloc(sizeof(LinkList));
//創建鏈表(n個節點)
LinkListCreate(head,n);
//輸出已建鏈表
LinkListPrintf(head);
//就地反轉
LinkListRerverse(head);
//輸出反轉後結果
LinkListPrintf(head);
}
return 0;
}
最後更新：2017-04-03 14:53:41