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。
