1，給定一個鏈表，要求寫一個算法來判斷其是否存在環(huán)？解答：這個題目的思路還是比較明晰的，就用大步小步法（就如同在一個圓形跑道中進(jìn)行長跑比賽，一個人A以速度2m/s跑步，另一個人B以速度3m/s跑步，他們從同一起點(diǎn)開始跑步，那么在有限的時間內(nèi)，他們必然會第二次相遇）應(yīng)用到這個題目，就是我們選取兩個指針p和q, p每次往前掃描1步，q每次往前掃描2步，那么如果鏈表存在圈，那么p和q一定會再次相遇，否則就不會相遇。循環(huán)結(jié)束的條件是要么他們倆相遇，要么其中一個指針運(yùn)行到頭。算法如下：bool circle_detect(Node *head) ? ?//輸入為要檢測鏈表的指針{if ( head == NULL)return false;Node *p = head;Node *q = head;p = p->next;q = (q->next)->next;while (p != NULL && q != NULL){if( p == q)return true;p = p->next;
q = (q->next)->next;}return false;}進(jìn)一步還可以得到鏈表進(jìn)入圈的起始點(diǎn)和圈的周長。在p和q相遇之后，將p移回到鏈表頭部然后p和q保持1的步長前進(jìn)，直到相遇，那么哪個點(diǎn)就是起始點(diǎn)，進(jìn)一步通過起始點(diǎn)遍歷一周就獲得了周長
2，給定一個鏈表，每個節(jié)點(diǎn)出了next指針之外，還有一個other指針，next指針指向該節(jié)點(diǎn)的下一個節(jié)點(diǎn)，而other指針可以指向該鏈表中任意一個節(jié)點(diǎn)或者為空，要求寫一個算法來復(fù)制這個鏈表？解答：這個題目是Google曾經(jīng)的一道面試題目，假設(shè)原始鏈表長度為n，這道題目一個最直接的想法就是先利用next指針重構(gòu)鏈表，然后再遍歷新鏈表，根據(jù)原始鏈表每一個元素的other指針指向的元素，然后在新鏈表中尋找該元素（關(guān)鍵字域相同），并設(shè)置當(dāng)前訪問的節(jié)點(diǎn)的other指針指向這個元素，這個過程需要 O(n^2)的訪問操作，而且如果鏈表元素中存在key值相同的元素，這個方法就不適用了。我們知道上面這個算法，比較耗時的一步操作是在設(shè)置新鏈表的other指針時，每次都要從頭開始查找對應(yīng)的元素，解決這個問題的一個辦法就是我們在用next指針建立新鏈表的時候?yàn)樾屡f鏈表的元素建立一個哈希表（通過關(guān)鍵字key域來建立映射），這樣第二次遍歷的時候，查找other指針對應(yīng)元素的時候只需要O(1)的哈希計(jì)算查表時間，就可以得到新鏈表對應(yīng)的元素，而且可以解決重復(fù)元素出現(xiàn)的情況，因而總的訪問時間就是O(2n)，但是這個方案需要O(n)的存儲代價。一個更好的方案是需要O(2n)的時間和O(1)的空間，就可以完成鏈表的復(fù)制，未完待續(xù)。

3，給定兩個有序鏈表，要求以O(shè)(n)時間復(fù)雜度將兩個鏈表合并，且合并后的鏈表還是有序的。接口定義如下Node *Merge(Node *h1, Node *h2){}解答：這個題目最簡單的一個想法就是插入排序，就是把h2的鏈表的元素逐個插入到h1的鏈表當(dāng)中，算法顯然是O(n^2)的，不符合要求。下面我們給出一個O(n)的merge過程，核心還是從把h2插入到h1當(dāng)中，但是在h1中記錄一個當(dāng)前插入鏈表的指針，這個指針只需至多掃描一遍h1，就可以將h2的元素插入到h1中，并保持有序。Node *Merge(Node *h1, Node *h2){if(h1==NULL)return h2;if(h2==NULL)return h1;Node *prev=NULL; ? ?//記錄前驅(qū)結(jié)點(diǎn)Node *curr=h1; ? ?//記錄當(dāng)前訪問的節(jié)點(diǎn)while(h2!=NULL){while(curr!=NULL && curr.key < h2.key)
{pre=curr;curr=curr.next;}if(curr==NULL){//當(dāng)前h1掃描完畢，直接將剩下的h2接到h1的末尾，返回h1prev.next=h2return h1;}else if(prev==NULL){//將鏈表h2的頭插入到h1的頭前面prev=h2; ? ? ?//更新prev到新插入的元素h2=h2.next; ? //更新h2prev.next=curr;}else{//將鏈表h2的頭插入到h1中間prev.next=h2;prev=prev.next ?//更新prev到新插入的元素h2=h2.next; ??//更新h2prev.next=curr; ?}}return h1;}

轉(zhuǎn)載于:https://www.cnblogs.com/kevinLee-xjtu/archive/2011/11/26/2299111.html

總結(jié)

以上是生活随笔為你收集整理的关于链表的一些问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。