50 lines
1.3 KiB
Markdown
50 lines
1.3 KiB
Markdown
# 链表-排序
|
||
|
||
|
||
|
||
|
||
## 链表排序
|
||
|
||
Given a head pointer pointing to a linked list ,please write a function that sort the list
|
||
in increasing order. You are not allowed to use temporary array or memory copy (微软面试题)
|
||
|
||
```
|
||
struct
|
||
{
|
||
int data;
|
||
struct S_Node *next;
|
||
}Node;
|
||
|
||
Node * sort_link_list_increasing_order (Node *pheader):
|
||
```
|
||
|
||
|
||
## 单链表归并排序
|
||
|
||
啥是归并排序？
|
||
|
||
|
||
|
||
|
||
类似的题有：
|
||
|
||
1 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
|
||
|
||
如果head1==head2，那么显然相交，直接返回head1。
|
||
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，
|
||
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
|
||
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
|
||
否则说明两个链表没有交点。
|
||
|
||
|
||
2 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
|
||
|
||
运用题一，我们可以检查链表中是否有环。如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next,
|
||
p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，
|
||
于是运用题二的方法，我们找到它们的第一个交点即为所求。
|
||
|
||
|
||
|
||
|
||
|