巩固一下基础，我重新写了一下无头节点单链表及链表面试题。我会分为入门，基础，进阶三章进行总结，点击以下蓝色字直接跳转对应章节。
链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶
链表头文件与基本实现在链表及链表面试题（一）入门中，此处不再赘述。
- 从尾到头打印单链表
//不改变链表结构，从尾到头打印单链表 （递归实现）
void PrintListRevers_Recursively(pList phead)
{
if (phead)
{
if (phead->next)
{
PrintListRevers_Recursively(phead->next);
}
printf("%d ", phead->data);
}
}
当链表非常长的时候，递归实现的会导致函数调用层级很深，可能导致调用栈溢出。用栈不会出现此类情况，显然用栈实现代码的鲁棒性会好一些。
//不改变链表结构，从尾到头打印单链表（栈实现）
void PrintListRevers_Stack(pList phead)
{
stack<pNode>nodes;
pNode cur = phead;
while (cur)
{
nodes.push(cur);
cur = cur->next;
}
while (!nodes.empty())
{
cur = nodes.top();
printf("%d ", cur->data);
nodes.pop();
}
}
- 删除一个无头节点单链表的非尾节点
void DeleteNotTailNode(pNode pos)
{
if (pos == NULL)
return;
pNode tmp = pos->next;
pos->data = tmp->data;
pos->next = tmp->next;
free(tmp);
tmp = NULL;
}
- 在无头节点单链表的非头结点一个节点前插入一个节点
void InsertNotHeadNode(pNode pos, DataType d)
{
assert(pos);
pNode tmp = BuyNode(pos->data);
tmp->next = pos->next;
pos->next = tmp;
pos->data = d;
}
- 单链表实现约瑟夫环
//单链表实现约瑟夫环
pNode Joseph(pList plist, const int x)//默认从第一个开始，所以只传两个值
{
pNode cur = plist;
pNode head = plist;
pNode prev = NULL;
if (plist == NULL || x <= 0)
return NULL;
while (cur->next) // 成环
cur = cur->next;
cur->next = head;
cur = cur->next;
while (cur != cur->next)
{
int count = x;
while (count--)
{
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
prev->data = cur->data;
free(cur);
cur == NULL;
cur = prev;
}
return cur;
}
- 逆置/反转单链表
//逆置链表
void ReverseList(pList* pplist)
{
assert(pplist);
pNode cur = *pplist;
pNode newhead = *pplist;
if (cur == NULL || cur->next == NULL)
return;
while (cur->next)
{
pNode tmp = cur->next;
cur->next = tmp->next;
tmp->next = newhead;
newhead = tmp;
}
*pplist = newhead;
}
- 单链表排序（冒泡排序 & 快速排序 & 选择排序）
常用排序算法时间复杂度和空间复杂度
冒泡排序的最坏时间复杂度为O(n^2)
//冒泡排序
void BubbleSort(pList* pplist)
{
assert(pplist);
pNode p = NULL;
pNode q = NULL;
for (p = *pplist; p != NULL; p = p->next)
{
for (q = p->next; q != NULL; q = q->next)
{
if (p->data > q->data)
{
DataType tmp;
tmp = p->data;
p->data = q->data;
q->data = tmp;
}
}
}
}
快速排序是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。
** 快速排序采用的思想是分治思想。**
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
//快速排序
void Quicksort(pNode begin, pNode end)
{
if (begin == NULL || end == NULL)
return;
DataType K = begin->data;
pNode slow = begin;
pNode fast = begin->next;
if (begin != end)
{
while (fast != NULL)
{
if (fast->data < K)
{
slow = slow->next;
DataType tmp = fast->data;
fast->data = slow->data;
slow->data = tmp;
}
fast = fast->next;
}
DataType tmp1 = slow->data;
slow->data = begin->data;
begin->data = tmp1;
Quicksort(begin, slow);
Quicksort(slow->next, end);
}
}
选择排序的最坏时间复杂度为O(n^2)。
两个元素一个走外层pNode out一个走内层pNode in，内层元素与外层元素比较大小。内层先遍历，如果升序排列，遇到小的元素则将小的的值交换到外层元素，内层走完一遍后，最小的已经在最前面了，然后外层走向下一个元素，内层继续从外层的下一个元素开始遍历重复之前动作，直至外层也遍历完成，整个排序结束。选择排序是** 不稳定的排序 **方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
//选择排序
void SelectionSort(pList plist)
{
assert(plist);
pNode out= plist;
pNode in = NULL;
for (; out!= NULL; out = out->next)
{
for (in = out->next; in != NULL; in = in ->next)
{
if (out->data > in ->data)
{
DataType tmp = out->data;
out->data = in->data;
in->data = tmp;
}
}
}
}
- 合并两个有序链表,合并后依然有序
pList Merge(pList list1, pList list2)
{
if (list1 == NULL)//返回条件
return list2;
if (list2 == NULL)//返回条件
return list1;
pList newlist = NULL;
if (list1->data < list2->data)
{
newlist = list1;
newlist->next = Merge(list1->next, list2); // 递归
}
else
{
newlist = list2;
newlist->next = Merge(list1, list2->next); // 递归
}
return newlist;
}
- 查找单链表的中间节点，要求只能遍历一次链表
pNode FindMiddleNode(pList list)
{
if (list == NULL)
return NULL;
pNode fast = list;
pNode slow = list;
while (fast && fast->next) //判断顺序不能颠倒
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
- 查找单链表的倒数第k个节点，要求只能遍历一次链表
//FindKthToTail
pNode FindKthToTail(pList list, unsigned int k)
{
if (list == NULL || k == 0) //注意鲁棒性，容易忽略(参数检查)
return NULL;
pNode prev = list;
pNode cur = NULL;
for (unsigned int i = 0; i < k - 1; ++i)
{
if (prev->next != NULL)
prev = prev->next;
else
return NULL; //注意鲁棒性，容易忽略(节点个数小于k)
}
cur = list;
while (prev->next)
{
prev = prev->next;
cur = cur->next;
}
return cur;
}
//test find middle/find k
void testFind()
{
pList plist;
InitList(&plist);
PushBack(&plist, 1);
PushBack(&plist, 2);
PushBack(&plist, 3);
PushBack(&plist, 4);
PushBack(&plist, 5);
PushBack(&plist, 6);
PrintList(plist);
//printf("%d \n", FindMiddleNode(NULL)->data);
printf("%d \n", FindMiddleNode(plist)->data);
for (int i = -1; i < 7; ++i)
{
pNode ret = FindKthToTail(plist, i);
if (ret)
printf("%d ", ret->data);
}
printf("\n");
}
网友评论