- 設(shè)計(jì)一個(gè)遞歸算法划提，刪除不帶頭結(jié)點(diǎn)的單鏈表L中的所有值為x的結(jié)點(diǎn)崔涂。
void delX(linkList &L, int x) {
Node *p;
if (L == NULL) return;
if (L->data == x) {
p = L;
L = L->pNext;
free(p);
delX(L, x);
}
else delX(L->pNext, x);
}
- 在帶頭結(jié)點(diǎn)的單鏈表L中关顷，刪除所有值為x的結(jié)點(diǎn)糊秆，并釋放其空間，假設(shè)值為x的結(jié)點(diǎn)不唯一议双。
void delX_1(linkList &L, int x) {
Node *p = L->pNext, *pre = L, * q;
while (p!=nullptr){
if (p->data == x) {
q = p;
p = p->pNext;
pre->pNext = p;
free(q);
}
else {
pre = p;
p = p->pNext;
}
}
}
void delX_2(linkList &L, int x) {
Node *p = L->pNext, *r = L, *q;
while (p != nullptr) {
if (p->data != x) {
r->pNext = p;
r = p;
p = p->pNext;
}
else {
q = p;
p = p->pNext;
free(q);
}
}
r->pNext = nullptr;
}
- 設(shè)L為帶頭結(jié)點(diǎn)的單鏈表扩然，編寫(xiě)算法實(shí)現(xiàn)從尾到頭反向輸出每個(gè)結(jié)點(diǎn)的值。
void reverse_traverse(linkList L,int cnt) {
Node *p = L->pNext;
if (p) {
reverse_traverse(p, cnt + 1);
if (cnt) cout << p->data << " ";
else cout << p->data << endl;
}
}//我?guī)Я烁袷交敵?- 試編寫(xiě)在帶頭結(jié)點(diǎn)的單鏈表L中刪除一個(gè)最小值結(jié)點(diǎn)的高效算法（假設(shè)最小值結(jié)點(diǎn)是唯一的）
void deleteMin(linkList &L) {
Node *p = L->pNext, *pre = L,*minNode = p , *minNodePre = L;
while (p != nullptr) {
if ( p->data < minNode->data ) {
minNode = p;
minNodePre = pre;
}
pre = p;
p = p->pNext;
}
minNodePre->pNext = minNode->pNext;
free(minNode);
}
- 試編寫(xiě)算法將帶頭指針的單鏈表就地逆置聋伦，輔助空間復(fù)雜度為O(1)
void reverse_1(linkList &L) {
Node *p = L->pNext, *next;
L->pNext = nullptr;
while (p) {
next = p->pNext;
p->pNext = L->pNext;
L->pNext = p;
p = next;
}
}
void reverse_2(linkList &L) {
Node *p = L->pNext, *next = p->pNext;
Node *pre;
p->pNext = nullptr;
while (next) {
pre = p;
p = next;
next = next->pNext;
p->pNext = pre;
}
L->pNext = p;
}
- 有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L夫偶，設(shè)計(jì)一個(gè)算法使其元素遞增有序。
void sort_increase(linkList &L) {
Node *p = L->pNext, *pre;
Node *r = p->pNext;
p->pNext = nullptr;
p = r;
while (p) {
r = p->pNext;
pre = L;
while (pre->pNext != nullptr && pre->pNext->data < p->data)
pre = pre->pNext;
p->pNext = pre->pNext;
pre->pNext = p;
p = r;
}
}
- 設(shè)在一個(gè)帶表頭結(jié)點(diǎn)的單鏈表中所有元素結(jié)點(diǎn)的數(shù)據(jù)值無(wú)序觉增，編寫(xiě)一函數(shù)兵拢，刪除表中所有介于給定的兩個(gè)值之間的元素。
void del_between_AandB(linkList &L, int a, int b) {
Node *p = L->pNext, *pre = L;
while (p) {
if (p->data >= a && p->data <= b) {
Node *temp = p;
p = p->pNext;
pre->pNext = p;
free(temp);
}
else {
pre = p;
p = p->pNext;
}
}
}
- 給定兩個(gè)單鏈表逾礁，找出兩個(gè)鏈表的公共結(jié)點(diǎn)说铃。
linkList search_first_common(linkList L1, linkList L2) {
int len1 = length(L1), len2 = length(L2);
int sub = abs(len1 - len2);
linkList long_list, short_list;
if (len1 > len2) long_list = L1->pNext, short_list = L2->pNext;
else long_list = L2->pNext, short_list = L1->pNext;
while (sub--) long_list = long_list->pNext;
while (long_list) {
if (long_list == short_list) return long_list;
else long_list = long_list->pNext, short_list = short_list->pNext;
}
if (long_list == nullptr)
return nullptr;
}
- 給定一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，按遞增次序輸出單鏈表中各個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素嘹履，并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間腻扇。（不允許使用數(shù)組作為輔助空間）
void print_increase(linkList &L) {
linkList pre, p;
while (L->pNext) {
pre = L;
p = pre->pNext;
while (p->pNext) {
if (p->pNext->data < pre->pNext->data)
pre = p;
p = p->pNext;
}
cout << pre->pNext->data;
linkList temp = pre->pNext;
pre->pNext = temp->pNext;
free(temp);
}
free(L);
}
- 將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使得A中含有原表中序號(hào)為奇數(shù)的元素砾嫉，B中含有原表中序號(hào)為偶數(shù)的元素幼苛，保持相對(duì)順序不變。
void split_list_to_a_b(linkList L, linkList a, linkList b) {
Node *p = L;
int i = 0;
Node *pa = a;
Node *pb = b;
while (p->pNext) {
if (i % 2 == 1) {
pa->pNext = p->pNext;
pa = pa->pNext;
p = p->pNext;
print_node(pa);
}
else {
pb->pNext = p->pNext;
pb = pb->pNext;
p = p->pNext;
print_node(pb);
}
i++;
}
pa->pNext = nullptr;
pb->pNext = nullptr;
}
- 在一個(gè)線性遞增的有序單鏈表中焕刮，有數(shù)值相同的元素存在舶沿，設(shè)計(jì)算法去除數(shù)值相同的元素墙杯，使表中不再有重復(fù)的元素。
void uniquify_sortedList(linkList L) {
linkList p = L->pNext, temp = p;
while (p->pNext) {
temp = p->pNext;
if (temp->data == p->data) {
p->pNext = temp->pNext;
free(temp);
}else p = p->pNext;
}
}
哇題目好多括荡，寫(xiě)到暈厥８吒洹！加上鏈表實(shí)現(xiàn)快400行代碼了畸冲。嫉髓。
下次再補(bǔ)！邑闲！
