資料結構--逆序一個單連結清單

這個問題有兩種解法。

第一種，我取名叫尾删頭插法：

核心思路：将每一次oldhead後面的tmp節點删除，并将該節點頭插，依次循環。直到oldhead變成連結清單的尾部，即tmp為空，循環結束。

如下圖單連結清單：oldhead為逆序前原單連結清單的頭，head為每逆置一次的單連結清單的新頭，tmp為每一次要被删除的節點。過程1表尾删，過程2表示頭插。

方法代碼：

void SListReverse1(SListNode **pphead)
{
//這裡我是通過二級指針**pphead來通路的頭部，還可以通過将頭部封裝成一個結構體直接通路。
	SListNode *head = *pphead;//每次循環中始終指向目前連結清單的頭
	SListNode *tmp = head->next;//每次循環中始終指向被删的節點
	SListNode *oldhead = *pphead;//每次循環中始終指向被删的前一個節點

	while (tmp)//tmp為空，代表逆序結束
	{
		oldhead->next = tmp->next;//架空tmp（後删）的一部分
		tmp->next = head;//讓tmp變成新頭（頭插）
		head = tmp;//換頭
		tmp = oldhead->next;//讓tmp變成下一次循環中待删除的節點
	}
	*pphead = head;
}
           

第二種，我取名叫依次改指向法：

核心思路：找到原頭部後面的每一個節點，依次讓它指向每一次新的頭部。

如下圖：pre為每一次變換後連結清單的頭部，cur為需要變換指向的節點，next為該節點等候一個節點，便于找到下一次需要變換的目标節點。

方法代碼：

void SListReverse2(SListNode **pphead)
{
	SListNode *pre = *pphead;
	SListNode *cur= pre->next;//被執行操作的節點
	SListNode *next = cur;//被執行操作的後一個節點,暫時指在cur，在循環開始的時候跳轉到其後一個節點

	pre->next = NULL;//此時的頭，将會成為尾，是以要設定尾節點 
	while (next)
	{
		next = next->next;//放前面避免next為空。
		cur->next = pre;//改變箭頭方向
		pre = cur;//循環節點依次後移
		cur = next;
	}
	*pphead = pre;//循環跳出時，cur和next都指向空，此時的頭為pre
}
           

總結

1.不能忘記将新頭賦給*pphead。

2.要注意兩種方法結束循環時的判定條件。

最後再給出我的單連結清單的節點結構體定義：

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode *next;
}SListNode;