【資料結構】課後作業——連結清單分離

P37.11

有一個整型連結清單，元素為{a1,b1,a2,b2,......,an,bn}。将其分離為A、B兩個連結清單，使得

A={a1,a2,......,an},B={bn,......,b2,b1}。

（1）算法的基本設計思想

周遊原連結清單，取第一個元素尾插到A，第二個元素頭插到B。以此類推。

連結清單具有頭結點，是以需要從頭結點的後繼開始。

注意頭插時遇到的問題，頭插法是把B的頭指針指向目前節點，然後目前節點指向B頭指針原來指的節點。那麼便會出現如下情況：目前節點原來指向的指針消失了，我們無法找到那個節點。那麼就需要使用一個新的指針來指向那個節點，來儲存它。要明确這一點：“改變一個節點的next指針，是改變該節點指向哪裡，原來指向的那個對象本身沒有變化”。知道這一點就不容易出錯了。

（2）代碼如下

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
void printList(LinkList &L)
{
	printf("\n");
	LNode *s = L->next;
	while (s != NULL)
	{
		printf("%d ", s->data);
		s = s->next;
	}
}
LinkList CreatListend(LinkList &L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf("%d", &x);
	while (x != 9999)
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}void Split(LinkList &L,LNode *A,LNode *B)
{
	LNode *Aend = A;//尾插法
	LNode *Bfirst = NULL;//頭插法
	LNode *Lnext;
	LNode *p = L->next;
	while (p!= NULL)
	{
		/*Aend->next = L->next;   原思路是懶得設指針p，直接用L->next代替，這樣在向後移動的時候，
		Aend = Aend->next;        就有L->next->next需要儲存，我沒有儲存它。
		B->next = L->next->next;  
		B->next->next = Bfirst;   這裡使得L斷裂了，中間出現了NULL，又沒有設指向之後元素的指針，之後的元素全部丢失。
		Bfirst = B->next;
		L = L->next->next;*/
		Aend->next = p;           //這裡設定了指針p，但實際上用L->next代替完全可以，隻不過可讀性變差
		Aend = Aend->next;        //那麼對比上下的代碼
		Lnext = p->next->next;    //出錯原因在于沒有儲存這個L->next->next->next，實際上在debug的時候我儲存過，隻不過儲存的是L->next->next，儲存錯了
		B->next = p->next;
		B->next->next = Bfirst;
		Bfirst = B->next;
		p = Lnext;
	}
	Aend->next = NULL;
}
void main()
{
	int count;
	LinkList L;
	LNode *A, *B;
	A = (LNode *)malloc(sizeof(LNode));
	B = (LNode *)malloc(sizeof(LNode));
	CreatListend(L);
	Split(L, A, B);
	printList(L);
	printList(A);
	printList(B);
}
           

（3）複雜度

時間複雜度O(n)

空間複雜度O(1)

PS：建議在對連結清單進行操作時，多使用結點指針，而不是直接L=L->next，太容易出錯。