倒置連結串列

        最近看了很多對於連結串列的操作,對連結串列的操作無非就是對指標的操作,因此,經常會使人暈頭轉賬,今天跟大家分享一個邏輯不是很複雜,但是對指標的操作較為複雜的一個例子—-倒置連結串列。

        顧名思義,倒置連結串列就是將一個連結串列裡的資料顛倒過來,使得原來的頭成為尾部,原來的尾部變成第一個節點。當然,一個簡單的方法,可以每次都取得當前連結串列的最後一個節點,將其前插到新生成的連結串列的第一個節點的位置,再將該節點釋放,最後把新生成的連結串列的頭結點首地址賦給原先連結串列的頭結點首地址。但是,這樣做不管是時間複雜度還是空間複雜度,都是比較高的,而如果可以只更改連結串列裡的每個節點的next成員的指向,效率則會大大提高。

        首先我們分析它的手工過程:我們首先要明確連結串列裡的數值遍歷的原理以及各個節點的指向關係。我們用一幅圖來清晰地表示。

        完成倒置連結串列有以下幾點需要注意:

        1、我們現在要做的就是使head的值變成#5,#1中next成員的值變為NULL,#2中next成員的值變為#1,#3中next成員的值變為#2… …同時還要滿足能夠遍歷整個連結串列,依次更改每一個節點中next的值,不能出現更改後無法找到下一個節點的情況。比如#2的next成員更改為了#1,當希望繼續找到#3時,原來next空間中儲存的#3的地址值已經被覆蓋為#1了,因此就不能繼續修改#3中next成員的值了,而且還會造成記憶體洩漏。

        2、我們發現需要將當前節點的next成員修改為當前節點的前一個節點的首地址,這就要求我們每次修改完能夠將當前節點的首地址儲存起來。而當前節點的首地址又是它的前驅節點的next成員沒有更改時的值。

        3、第一個節點和最後一個節點情況較為特殊,因為第一個節點的next成員被更改為NULL,而末節點的首地址又應該賦值給head。

        知道了以上三點我們就可以開始程式設計了:

        1、我們需要一個變數now用來遍歷連結串列,而更改這個變數的時機必須在我們修改當前節點的next成員之前。

        2、需要一個用來儲存當前節點的前驅節點的地址的變數preNode。

        3、每次應先將preNode的值賦值給now的next成員,再將now的值賦值給preNode。

        4、preNode的初值應為NULL,而不應該是#1,因為我們遍歷肯定是從第一個節點開始遍歷,第一個節點的前一個節點當然應該是空,這樣做,一是符合語義性,二是根據我們之前所說的操作“每次將preNode的值賦值給now的next成員”,可以不用單獨處理第一個節點,就能夠保證第一個節點的next成員的值為NULL。

        5、在最後,我們應該將now的值賦值給head,因為迴圈結束時,now的值一定是原先連結串列的最後一個節點。

具體程式碼如下:

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

typedef struct NODE{
	int data;
	struct NODE *next;
}NODE;

void initLine(NODE **head);
void destoryLine(NODE **head);
void showLine(NODE *head);
void upSideDownLine(NODE **head);

void upSideDownLine(NODE **head) {
	NODE *now = *head;
	NODE *preNode = NULL;
	NODE *temp;

	while (now != NULL) {
		temp = now->next;
		now->next = preNode;
		preNode = now; 
		now = temp;
	}
	*head = preNode;
}

void showLine(NODE *head) {
	NODE *p;

	printf("\n");
	for (p = head; p != NULL; p = p->next) {
		printf("%d ", p->data);
	}
	printf("\n");
}

void destoryLine(NODE **head) {
	NODE *p;

	if (*head == NULL) {
		return;
	}

	while(*head != NULL) {
		p = *head;
		*head = p->next;
		free(p);
	}
}

void initLine(NODE **head) {
	int num;
	NODE *p = *head;

	if (*head != NULL) {
		return;
	}
	printf("請輸入一個數(-1表示結束輸入):");
	scanf_s("%d", &num);
	while (num != -1) {
		if (*head == NULL) {
			*head = (NODE *)calloc(1, sizeof(NODE));
			(*head)->data = num;
			p = *head;
		}
		else {
			p->next = (NODE *)calloc(1, sizeof(NODE));
			p->next->data = num;
			p = p->next;
		}
		printf("請輸入一個數(-1表示結束):");
		scanf_s("%d", &num);
	}
}

void main(void) {
	NODE *head = NULL;

	initLine(&head);
	showLine(head);
	upSideDownLine(&head);
	showLine(head);
	destoryLine(&head);

	fflush(stdin);
	getchar();
}