1. 对单链表排序，用代码实现【腾讯】
typedef struct Node {
int data;
struct Node *pNext;
} NODE, *PNODE;
//链表的长度
int length_list(PNODE pHead) {
PNODE p = pHead->pNext;
int len = 0;
while (NULL != p) {
++len;
p = p->pNext;
}
return len;
}
//对链表排序
void sort_list(PNODE pHead) {
int i, j, t;
int len = length_list(pHead);
PNODE p, q;
for (i = 0, p = pHead->pNext; i < len - 1; ++i, p = p->pNext) {
for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext) {
if (p->data > q->data) {
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
}
2. 快速找到未知长度的单链表的中间节点【腾讯】
- 普通方法：
遍历一遍单链表以确定单链表的长度L, 然后再次从头结点出发循环L/2次找到单链表的中间节点。
算法复杂度：O(L + L/2)=O(3L/2)。 - 利用快慢指针原理：
设置两个指针search, mid都指向单链表的头结点。其中search的移动速度是mid的两倍。但*search指向末尾节点的时候，mid正好在中间了。
代码实现(C语言)
typedef int ElemType;
typedef struct Node
{
ElemType data; //数据域
struct Node *next; //指针域
} Node;
typedef struct Node *LinkList;
//快速找到未知长度单链表的中间节点 L:链表的头结点 *e返回的链表中间节点
bool GetMidNode(LinkList L, ElemType *e) {
LinkList search, mid;
mid = search = L;
while (search->next != NULL) {
if (search->next->next != NULL){
search = search->next->next;
mid = mid->next;
} else {
search = search->next;
}
}
*e = mid->data;
return true;
}
持续努力更新中......
