鏈表面試題之常規題1 -- 反轉鏈表

作者: cnyao 來源: 博客園發布時間: 2009-11-26 21:42 閱讀: 2352 次推薦: 0 原文鏈接 [收藏]

反轉鏈表其實在前面的系列中已經寫過程序了，現在只是將其單獨提出來，列在這里。

主要就是使用額外的指針來標識新鏈表的頭，現在正在處理的鏈表，以及鏈表的next節點。

題目：將鏈表按照逆序排列

可以使用非遞歸，也就是循環遍歷的方法

1 linknode *reverse(linknode* head)
2 {
3     linknode *newlist=NULL;
4     linknode *curr=head;
5     while(curr)
6     {
7         //定義一個指向當前節點下一個節點的指針
8         linknode *next=curr->next;
9         //將當前節點的next指針進行反轉
10         curr->next=newlist;
11         //將新的反轉后的鏈表的頭節點移動到當前節點
12         newlist=curr;
13         //移動到下一個節點，準備處理
14         curr=next;
15     }
16     return newlist;
17 }
18

利用參數，少用一個節點的空間

1 linknode *reverse(linknode *head)
2 {
3     linknode *newlist=NULL;
4     linknode *curr=head;
5     while(curr)
6     {
7         head=curr->next;
8         curr->next=newlist;
9         newlist=curr;
10         curr=head;
11     }
12     return newlist;
13 }

使用遞歸來實現反轉鏈表

1 linknode* reverse(linknode *oldlist, linknode *newlist)
2 {
3     if(oldlist==NULL)
4         return newlist;
5     linknode *next=oldlist->next;
6     oldlist->next=newlist;
7     reverse(next,oldlist);
8 }
9

如果有空，還會有一篇討論約瑟夫環問題。

這里還有一道題目可以作為思考題。

題目如下：

有一個特殊的鏈表，其中每個節點不但有指向下一個節點的指針pNext，還有一個指向鏈表中任意節點的指針pRand，如何copy這個鏈表？

鏈表節點為