单链表的基本实现:https://blog.csdn.net/qq_41078889/article/details/90603873
以下这些功能的实现依赖上一篇博客单链表的基本实现(有头结点)。
- 单链表的排序(冒泡)
- 单链表的倒数第K个值(只能遍历一遍单链表)
- 逆置单链表
- 两个单链表的合并问题
- 单链表的约瑟夫环问题
1.单链表的排序(冒泡)
对单链表的数据从小到大进行排序,根据冒泡 排序的原理完成
//对链表数据进行排序
void Sort(List list)
{
Node *tmp1 = list->next;
Node *tmp2 = nullptr;
assert(tmp1 != nullptr);
for (tmp1 = list->next; tmp1->next != NULL; tmp1 = tmp1->next)
{
for (tmp2 = tmp1->next; tmp2 != NULL; tmp2 = tmp2->next)
{
if (tmp1->data > tmp2->data)
{
int val = tmp1->data;
tmp1->data = tmp2->data;
tmp2->data = val;
}
}
}
}
2.单链表的倒数第K个值(只能遍历一遍单链表)
定义两个指针两个指针分别往后走,第一个指针先走K步为快指针,第二个指针然后和第一个指针一起往后走,当第快指针走到最后面时,此时的慢指针刚好就是倒数第K个值。
//单链表倒数第K个的值
void FindKNode(List list, int k)
{
assert(list != nullptr);
Node* fast = list;
Node* slow = list;
while (fast->next != nullptr)
{
fast = fast->next;
if (--k <= 0)//这里就是控制慢指针的
{
slow = slow->next;
}
}
printf("%d\n", slow->data);
}
3.逆置单链表
//单链表的逆置1
void reveseList1(List list)
{
Node *p = list->next;//p为原链表当前处理的节点
Node *q = NULL;//q指针保留当前处理节点的下一个节点
list->next = NULL;//将原链表置为空
while (p != NULL)//当原链表还未处理完
{
q = p->next;//q指向正处理的下一个节点
p->next = list->next;//将p节点的地址接在p节点后面
list->next = p;//将头指针接在p节点上
p = q;//互换
}
}
4.两个单链表的合并问题
两个有序链表,合并后依然有序
Node *link_merge(List head1, List head2)
{
Node *newq = NULL, *tail = NULL;
Node *p = NULL, *q = NULL;
p = head1->next;
q = head2->next; //p q 分别指向第一个节点
if (p->data < q->data)
{ //比较第一个节点的大小 确定头结点的位置
newq = head1;
p = p->next;
}
else
{
newq = head2;
q = q->next;
}
tail = newq->next; //指向已排好序的1节点
while (p && q)
{ //将较小的节点链接到已排好序的尾节点tail后
if (p->data < q->data)
{
tail->next = p;
p = p->next;
}
else
{
tail->next = q;
q = q->next;
}
tail = tail->next;
}
if (p)
{ //将未排完的节点链接到tail后
tail->next = p;
}
else
{
tail->next = q;
}
return newq;
}
5.单链表的约瑟夫环问题
约瑟夫环(约瑟夫问题)是一个数学的应用问题:
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从头开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后剩余的节点即为原问题的解。
//约瑟夫环
void JosepRing(List list, int k)
{
assert(list != nullptr);
int count = k;
Node *cur = list;
Node *prev = nullptr;
while (cur->next != nullptr)
{
cur = cur->next;
}
cur->next = list->next; //链表形成环
cur = list->next;
while (cur->next != cur) //相等时只剩下一个节点
{
count = k;
while (--count)
{
prev = cur;
cur = cur->next;
}
//走到这里就开始删除,然后继续循环
printf("删除的数为%d \n", cur->data);
prev->next = cur->next;
free(cur);
cur = prev->next;
}
printf("最后一个人是 %d \n", cur->data);
}