- 设计一个递归算法，删除不带头结点的单链表L中的所有值为x的结点。
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);
}
- 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一。
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;
}
- 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
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;
}
}//我带了格式化输出
- 试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）
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);
}
- 试编写算法将带头指针的单链表就地逆置，辅助空间复杂度为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;
}
- 有一个带头结点的单链表L，设计一个算法使其元素递增有序。
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;
}
}
- 设在一个带表头结点的单链表中所有元素结点的数据值无序，编写一函数，删除表中所有介于给定的两个值之间的元素。
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;
}
}
}
- 给定两个单链表，找出两个链表的公共结点。
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;
}
- 给定一个带表头结点的单链表，按递增次序输出单链表中各个结点的数据元素，并释放结点所占的存储空间。（不允许使用数组作为辅助空间）
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);
}
- 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A中含有原表中序号为奇数的元素，B中含有原表中序号为偶数的元素，保持相对顺序不变。
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;
}
- 在一个线性递增的有序单链表中，有数值相同的元素存在，设计算法去除数值相同的元素，使表中不再有重复的元素。
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;
}
}
哇题目好多，写到晕厥！！加上链表实现快400行代码了。。
下次再补！！
