1.在非尾节点后插入一个节点
void Insert(SListNode *&pos, DateType x) //在非尾节点后插入一个节点
{
if (pos == NULL)
{
return;
}
SListNode *newNode = _BuyNode(pos->data);
newNode->next = pos->next;
pos->data = x;
pos->next = newNode;
}
2.删除无头节点的单链表非尾节点
void Erase(SListNode *&pos) //删除无头节点的单链表非尾节点
{
if (pos == NULL || pos->next == NULL)
{
return;
}
SListNode *next = pos->next;
pos->data = next->data;
pos->next = next->next;
free(next);
}
3.递归实现将单链表从尾节点打印到头节点
void PrintfTailToHead(SListNode *& pHead) // 递归实现将单链表从尾节点打印到头节点
{
SListNode *newpHead = pHead;
if (newpHead == NULL)
{
return;
}
else
{
PrintfTailToHead(newpHead->next);
printf("%d ", newpHead->data);
}
测试用例如下：
void Test3()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
PrintfTailToHead(seq);
}
运行结果如下：
4.逆置单链表
void ReverseList(SListNode *& pHead) //逆置单链表
{
if (pHead == NULL)
{
return;
}
SListNode *pCur = pHead;
SListNode *pNext = NULL;
SListNode *NewHead = NULL;
while (pCur)
{
pNext = pCur->next;
if (!pNext)
{
pHead = pCur;
}
pCur->next = NewHead;
NewHead = pCur;
pCur = pNext;
}
}
测试用例如下：
void Test4()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
ReverseList(seq);
PrintfSlist(seq);
}
运行结果如下：
5.找到单链表倒数第k个数
SListNode* FindNode(SListNode *pHead, DateType k) //找到单链表倒数第k个数
{
SListNode *fast = pHead;
SListNode *slow = pHead;
while (fast && k--)
{
if (fast == NULL)
{
return NULL;
}
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
测试用例如下：
void Test5()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
SListNode *ret=FindNode(seq, 2);
cout << ret->data<<endl;
}
运行结果如下：
6.找出单链表的最中间数
SListNode* FindMiddleNode(SListNode* pHead) //找出单链表的最中间数
{ //若单链表为偶数则返回的是最中间两个数中的第一个
if (pHead == NULL)
{
return NULL;
}
SListNode *fast = pHead;
SListNode *slow = pHead;
while (fast)
{
if (fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
else
fast = NULL;
}
return slow;
}
测试用例如下：
void Test6()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
SListNode *ret = FindMiddleNode(seq);
cout << ret->data<<endl;
}
运行结果如下：
7.约瑟夫环
SListNode * JosephLoop(SListNode *pHead,DateType k) //约瑟夫环
{
SListNode * NewNode = pHead;
SListNode *next;
while(1)
{
if (NewNode == NewNode->next)
{
return NewNode;
}
DateType t = k - 1;
while (t--)
{
NewNode = NewNode->next;
}
next = NewNode->next;
NewNode->data = NewNode->next->data;
NewNode->next = NewNode->next->next;
free(next);
}
}
测试用例如下：
void Test7()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
PushBack(seq, 6);
PushBack(seq, 7);
PushBack(seq, 8);
PushBack(seq, 9);
PushBack(seq, 10);
SListNode *tmp = Find(seq, 10); //找到尾节点的地址
tmp->next = seq; //将尾节点指向头结点，所以这样就会构成了一个环
SListNode * ret =JosephLoop(seq, 4); //利用该函数就可以找到剩下的最后一个数
printf("%d\n", ret->data);
}
运行结果如下：
8.用单链表进行冒泡排序
void Bubblesort(SListNode *pHead) //用单链表进行冒泡排序
{
if (pHead == NULL)
{
return;
}
SListNode * tail = NULL;
SListNode *cur = pHead;
SListNode *next = pHead->next;
while (tail != pHead->next)
{
cur = pHead;
next = pHead->next;
while (cur != tail && cur->next != tail)
{
if (cur->data > next->data)
{
DateType tmp = cur->data;
cur->data = next->data;
next->data = tmp;
}
cur = cur->next;
next = next->next;
}
tail=cur;
}
}
测试用例如下：
void Test8()
{
SListNode *seq = NULL;
PushBack(seq, 5);
PushBack(seq, 4);
PushBack(seq, 3);
PushBack(seq, 2);
PushBack(seq, 1);
PrintfSlist(seq);
printf("\n");
Bubblesort(seq);
PrintfSlist(seq);
printf("\n");
}
运行结果如下：
9.合并两个有序单链表
SListNode * MergeList(SListNode *head1, SListNode *head2) //合并两个有序单链表
{
if (head1 == NULL)
{
return head2;
}
else if (head2 == NULL)
{
return head1;
}
SListNode *head = NULL;
SListNode *p1 = NULL;
SListNode *p2 = NULL;
if (head1->data < head2->data)
{
head = head1;
p1 = head1->next;
p2 = head2;
}
else
{
head = head2;
p2 = head2->next;
p1 = head1;
}
SListNode* pcurrent = head;
while (p1 != NULL && p2 != NULL)
{
if (p1->data <= p2->data)
{
pcurrent->next = p1;
pcurrent = p1;
p1 = p1->next;
}
else
{
pcurrent->next = p2;
pcurrent = p2;
p2 = p2->next;
}
}
if (p1 != NULL)
{
pcurrent->next = p1;
}
if (p2 != NULL)
{
pcurrent->next = p2;
}
return head;
}
测试用例如下：
void Test9()
{
SListNode *seq1 = NULL;
SListNode *seq2 = NULL;
PushBack(seq1, 1);
PushBack(seq1, 2);
PushBack(seq1, 3);
PushBack(seq1, 4);
PushBack(seq1, 5);
PushBack(seq2, 6);
PushBack(seq2, 7);
PushBack(seq2, 8);
PushBack(seq2, 9);
PushBack(seq2, 10);
PrintfSlist(seq1);
cout << endl;
PrintfSlist(seq2);
cout << endl;
SListNode *ret=MergeList(seq1, seq2);
PrintfSlist(ret);
}
运行结果如下：
10.用递归合并两个有序单链表
SListNode * _MergeList(SListNode *head1, SListNode *head2) //用递归合并两个有序单链表
{
if (head1 == NULL)
{
return head2;
}
if (head2 == NULL)
{
return head1;
}
SListNode *head = NULL;
if (head1->data < head2->data)
{
head = head1;
head->next = _MergeList(head1->next, head2);
}
else
{
head = head2;
head->next = _MergeList(head1, head2->next);
}
return head;
}
11.判断单链表是否带环，若带环返回快慢指针相遇时地址
SListNode *JudgeLoop(SListNode *pHead) //判断单链表是否带环，若带环返回快慢指针相遇时地址
{
if (pHead == NULL)
{
return NULL;
}
SListNode * slow = pHead;
SListNode * fast = pHead->next;
while ((fast != slow) && fast)
{
slow = slow->next;
if (slow==NULL || fast->next==NULL)
{
return NULL;
}
if (slow != NULL)
{
fast = fast->next->next;
}
}
return fast;
}
测试用例如下：
void Test11()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
PushBack(seq, 6);
PushBack(seq, 7);
PushBack(seq, 8);
PushBack(seq, 9);
PushBack(seq, 10);
SListNode * address1 = Find(seq, 7);
SListNode * address2 = Find(seq, 3);
address1->next = address2;
SListNode * tmp=JudgeLoop(seq);
if (tmp == NULL)
{
printf("存在环\n");
}
else
{
printf("存在环，快慢指针相遇在节点%d\n", tmp->data);
}
}
单链表如图所示：
运行结果如下：
12.判断单链表是否带环，若带环返回环的个数
DateType CountLoop(SListNode *pHead) // 判断单链表是否带环，若带环返回环的个数
{
DateType count = 0;
if (pHead == NULL)
{
return 0;
}
SListNode * address=JudgeLoop(pHead);
if (address == NULL)
{
return 0;
}
SListNode *tmp = address->next;
address->next = NULL;
while (tmp)
{
count++;
tmp = tmp->next;
}
return count;
}
测试用例如下：
void Test12()
{
SListNode *seq = NULL;
PushBack(seq, 1);
PushBack(seq, 2);
PushBack(seq, 3);
PushBack(seq, 4);
PushBack(seq, 5);
PushBack(seq, 6);
PushBack(seq, 7);
PushBack(seq, 8);
PushBack(seq, 9);
PushBack(seq, 10);
SListNode * address1 = Find(seq, 10);
SListNode * address2 = Find(seq, 7);
address1->next = address2;
printf("%d\n", CountLoop(seq));
}
单链表如图所示：
运行结果如下：
这些就是单链表中的一些简单的运用。
本文出自 “零点时光” 博客，请务必保留此出处http://10741764.blog.51cto.com/10731764/1743028
原文：http://10741764.blog.51cto.com/10731764/1743028