单向链表的几道题

---------------------------------------------------------------------------

1. 转置单向链表 (也就是反序，注意链表的边界条件并考虑空链表)。

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/* Reverse the singly linked list *psll. */
void reverse_singly_linked_list(list * psll)
{
list h = NULL;
list p = *psll;

if (!psll || !*psll)
{
return;
}

while (p)
{
list tmp = p;
p = p->next;
tmp->next = h;
h = tmp;
}

*psll = h;
}

---------------------------------------------------------------------------

2. 在链表里如何发现循环链接？

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/* Check that whether there is loop in the singly linked list sll or not. */
int find_circle(list sll)
{
list fast = sll;
list slow = sll;

if (NULL == fast)
{
return -1;
}

while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;

if (fast == slow)
{
return 1;
}
}

return 0;
}


参考：
http://ostermiller.org/find_loop_singly_linked_list.html

---------------------------------------------------------------------------

3. 找到单向链表中间那个元素，如果有两个则取前面一个。

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/* Find the middle element of the singly linked list sll. */
list find_middle(list sll)
{
list slow = sll;
list fast = sll;

if (NULL == fast)
{
return NULL;
}

while (1)
{
if (NULL == fast->next || NULL == fast->next->next)
{
return slow;
}

slow = slow->next;
fast = fast->next->next;

/* Prevent that there is a loop in the linked list. */
if (fast == slow)
{
return NULL;
}
}
}

---------------------------------------------------------------------------

4. 删除单链表的倒数第 m 个元素。
给定一个单向链表 (长度未知)，请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第 m 个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/* Find the mth element of the singly linked list sll from the end. */
list find_the_mth_element_from_end(list sll, int m)
{
list fast = sll; /* Used for loop detecting. */
list ahead = sll;
list after = sll;

if (NULL == ahead || m <= 0)
{
return NULL;
}

while (m--)
{
if (NULL == ahead)
{
return NULL;
}
ahead = ahead->next;

if (fast && fast->next)
{
fast = fast->next->next;
if (fast == ahead)
{
return NULL;
}
}
}

while (1)
{
if (NULL == ahead)
{
return after;
}
ahead = ahead->next;
after = after->next;

if (fast && fast->next)
{
fast = fast->next->next;
if (fast == ahead)
{
return NULL;
}
}
}
}

---------------------------------------------------------------------------

5. 给定一个单向链表的头指针，要求找出该链表循环部分的第一个节点。如果该链表不是循环链表，则返回空指针。例如给定下面的链表：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
就应该返回结点 3 的指针。请优化时间和空间。

解法一：
一次遍历，把地址存入 hash 表就行了，第一次出现重复的地址就是需要的解。
时间复杂度 O(n)，空间复杂度 O(n)。

解法二：
把链表当做有向图，进行深度优先遍历，第一个回退边指向的节点即是需要的解。
时间复杂度 O(n)，空间复杂度 O(n)。

解法三：
首先根据链表创建一个逆序的链表。如下：
原始：1->2->3->4->5->6->7->8->(3)
逆序：1->2->3->8->7->6->5->4->(3)
然后分别从两个链表头指针开始，找到 next 指针不一样的那个节点就是最终目标了。
时间复杂度 O(n)，空间复杂度 O(n)。

解法四：
用两个步长分别为 1 和 2 的指针前进，第一次相遇之后再前进，第二次相遇时停止。记下从第一次相遇到第二次相遇，步长为 1 的指针走过的步数 S，则 S 为环的长度。然后用两个指针，一个在链头，一个走到链头后第 S 个位置上，同时以步长为 1 前进，判断两个指针是否相等，如果是就是环的起始位置了。
时间复杂度 O(n)，空间复杂度 O(1)。

解法五：(跟解法四的思想差不多，优于解法四，因为常数因子小)
用两个步长分别为 1 和 2 的指针前进，第一次相遇之后，令其中一个指针指向链表头。然后，令两个指针步长都为 1，同时前进，相遇时停止。该节点就是环的起始位置。
时间复杂度 O(n)，空间复杂度 O(1)。

下面给出解法五的 C 实现。

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/*
* Find the head node of the loop in the singly linked list sll.
* If there is not a loop in sll, NULL is return.
*/
list find_head_of_loop(list sll)
{
list slow = sll;
list fast = sll;

if (NULL == fast)
{
return NULL;
}

while (1)
{
if (NULL == fast->next || NULL == fast->next->next)
{
return NULL;
}

slow = slow->next;
fast = fast->next->next;

if (fast == slow)
{
slow = sll;
break;
}
}

while (1)
{
slow = slow->next;
fast = fast->next;

if (fast == slow)
{
return fast;
}
}
}


参考：
http://www.chinaunix.net/jh/23/896018.html

---------------------------------------------------------------------------

6. 给定一个单向链表的结点，要求在常数时间里删除该结点。

常数时间删除结点肯定不行，不过可以用假删除，就是把要删除节点的值用要删除节点的下一个节点值覆盖，然后删除下一个节点 (要求该节点的下一个节点不能是空) ：
p->data = p->next->data;
temp = p->next;
p->next = temp->next;
free(temp);

---------------------------------------------------------------------------