1.单线链表倒序/逆序:
struct Node
{
int data;
Node* next;
};
Node* Reverse(Node* head)
{
struct Node *prep,*nowp,*nextp;
prep=NULL;
nowp=head;
while(nowp!=NULL)
{
nextp=nowp->next;
nowp->next=prep;
prep=nowp;
nowp=nextp;
}
return prep;
}
2. 判断单向链表是否有环。下图的三种情形都视为有环，算法必须能处理它们。
01) 如果知道链表长度, 则可以遍历链表, 遍历次数大于长度, 就是有环了
int iLength; 链表长度, 已知
int i = 0;
while (p != NULL)
{
i ++;
if (i > iLength)
{
break;
return;
}
}
02)解法：设置两个指针，一个每次向前跳一步，一个跳两步，如果它们相遇，则有环。
bool fLinkedListHasCircle(const Node* p)
{
bool flag = false;
const Node* slowIterator = p;
const Node* fastIterator = p;
while(slowIterator && fastIterator->next)
{
slowIterator = slowIterator->next;
fastIterator = fastIterator->next->next;
if (slowIterator == fastIterator)
{
flag = true;
break;
}
}
return flag;
}
快速证明算法的正确性：
考虑一般的情形，假设环上有n个结点，把它们从0到n-1编号，假设slowIterator达到节点0时，fastIterator领先
slowIterator的距离为m，我们知道fastIterator在一圈之内必能追上slowIterator。假设x跳以后
fastIterator追上slowIterator，此时slowIterator所在的结点编号为x，而fastIterator所在的节点编号为
m+2x-n:
x = m+2x-n
x = n-m
所以经过n-m跳后，fastIterator追上slowIterator。
