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. 判斷單向鏈表是否有環(huán)。下圖的三種情形都視為有環(huán)，算法必須能處理它們。

01) 如果知道鏈表長度, 則可以遍歷鏈表, 遍歷次數(shù)大于長度, 就是有環(huán)了

   int iLength; 鏈表長度, 已知
   int i = 0;
   while (p != NULL)
   {
       i ++;
       if (i > iLength)
       {
           break;
           return;
       }
   }

02)解法：設置兩個指針，一個每次向前跳一步，一個跳兩步，如果它們相遇，則有環(huán)。

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;
}

快速證明算法的正確性：

考慮一般的情形，假設環(huán)上有n個結(jié)點，把它們從0到n-1編號，假設slowIterator達到節(jié)點0時，fastIterator領先 slowIterator的距離為m，我們知道fastIterator在一圈之內(nèi)必能追上slowIterator。假設x跳以后 fastIterator追上slowIterator，此時slowIterator所在的結(jié)點編號為x，而fastIterator所在的節(jié)點編號為 m+2x-n:

x = m+2x-n
x = n-m

所以經(jīng)過n-m跳后，fastIterator追上slowIterator。