链表 - 排序¶

链表排序¶

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 开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。