1：兩個連結清單找公共節點：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道微軟的面試題。微軟非常喜歡與連結清單相關的題目，是以在微軟的
面試題中，連結清單出現的機率相當高。
如果兩個單向連結清單有公共的結點，也就是說兩個連結清單從某一結點開始，它們的
m_pNext都指向同一個結點。但由于是單向連結清單的結點，每個結點隻有一個
m_pNext，是以從第一個公共結點開始，之後它們所有結點都是重合的，不可能
再出現分叉。是以，兩個有公共結點而部分重合的連結清單，拓撲形狀看起來像一個
Y，而不可能像 X。
看到這個題目，第一反應就是蠻力法：在第一連結清單上順序周遊每個結點。每周遊
一個結點的時候，在第二個連結清單上順序周遊每個結點。如果此時兩個連結清單上的結
點是一樣的，說明此時兩個連結清單重合，于是找到了它們的公共結點。如果第一個
連結清單的長度為 m，第二個連結清單的長度為 n，顯然，該方法的時間複雜度為 O(mn)。
接下來我們試着去尋找一個線性時間複雜度的算法。我們先把問題簡化：如何判
斷兩個單向連結清單有沒有公共結點？前面已經提到，如果兩個連結清單有一個公共結
點，那麼該公共結點之後的所有結點都是重合的。那麼，它們的最後一個結點必
然是重合的。是以，我們判斷兩個連結清單是不是有重合的部分，隻要分别周遊兩個
連結清單到最後一個結點。如果兩個尾結點是一樣的，說明它們用重合；否則兩個鍊
表沒有公共的結點。
在上面的思路中，順序周遊兩個連結清單到尾結點的時候，我們不能保證在兩個連結清單
上同時到達尾結點。這是因為兩個連結清單不一定長度一樣。但如果假設一個連結清單比
另一個長l個結點，我們先在長的連結清單上周遊 l個結點，之後再同步周遊，這個
時候我們就能保證同時到達最後一個結點了。由于兩個連結清單從第一個公共結點考
試到連結清單的尾結點，這一部分是重合的。是以，它們肯定也是同時到達第一公共
結點的。于是在周遊中，第一個相同的結點就是第一個公共的結點。
在這個思路中，我們先要分别周遊兩個連結清單得到它們的長度，并求出兩個長度之
差。在長的連結清單上先周遊若幹次之後，再同步周遊兩個連結清單，知道找到相同的結
點，或者一直到連結清單結束。此時，如果第一個連結清單的長度為 m，第二個連結清單的長
度為n，該方法的時間複雜度為 O(m+n)。
int length(node *list){ //求長度
int len=0;
while(list){
len++;
list=list->next;
}
return len;
}
node *find_node(node *&listA,node *&listB){
int lenA=length(listA),lenB=length(listB);
node *lA=listA,*lB=listB;
if(lenA>lenB){
for(int i=1;i<=lenA-lenB;i++)
lA=lA->next;
}else{
for(int i=1;i<=lenB-lenA;i++)
lB=lB->next;
}
while(lA&&lB){
if(lA==lB){
return lA;
}else{
lA=lA->next;
lB=lB->next;
}
}
return NULL;
}
2：連結清單裡有一個循環，求此點
有一個單連結清單，其中可能有一個環，也就是某個節點的next指向的是連結清單中在它之前的節點，這樣在連結清單的尾部形成一環。
問題：
1、如何判斷一個連結清單是不是這類連結清單？
2、如果連結清單為存在環，如果找到環的入口點？
解答：
1、最簡單的方法, 用一個指針周遊連結清單, 每遇到一個節點就把他的記憶體位址(java中可以用object.hashcode())做為key放在一個hashtable中. 這樣當hashtable中出現重複key的時候說明此連結清單上有環. 這個方法的時間複雜度為O(n), 空間同樣為O(n).
2、使用反轉指針的方法, 每過一個節點就把該節點的指針反向
Boolean reverse(Node *head) {
Node *curr = head;
Node *next = head->next;
curr->next = NULL;
while(next!=NULL) {
if(next == head) { /* go back to the head of the list, so there is a loop */
next->next = curr;
return TRUE;
}
Node *temp = curr;
curr = next;
next = next->next;
curr->next = temp;
}
/* at the end of list, so there is no loop, let's reverse the list back */
next = curr->next;
curr ->next = NULL;
while(next!=NULL) {
Node *temp = curr;
curr = next;
next = next->next;
curr->next = temp;
}
return FALSE;
}
看上去這是一種奇怪的方法: 當有環的時候反轉next指針會最終走到連結清單頭部; 當沒有環的時候反轉next指針會破壞連結清單結構(使連結清單反向), 是以需要最後把連結清單再反向一次. 這種方法的空間複雜度是O(1), 實事上我們使用了3個額外指針;而時間複雜度是O(n), 我們最多2次周遊整個連結清單(當連結清單中沒有環的時候).
這個方法的最大缺點是在多線程情況下不安全, 當多個線程都在讀這個連結清單的時候, 檢查環的線程會改變連結清單的狀态, 雖然最後我們恢複了連結清單本身的結構, 但是不能保證其他線程能得到正确的結果.
3、 這是一般面試官所預期的答案: 快指針和慢指針
設定兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果連結清單存在環，則fast必定先進入環，而slow後進入環，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環連結清單)
int is_link_list_cicled(Node* head)
{
Node *p = head, *q = head;
while(p && q)
{
p = p-> next;
q = q-> next;
if(!q)
return 0;
q = q-> next;
<pre name="code" class="cpp"> if(p == q)
return 1;
} return 0; }
證明步長法的正确性(追擊問題，如果有環則肯定可以相遇)：
如果連結清單有環，不妨假設其環長度為M（>=2）。p指針首次到達交點（N0）時，q指針已經進入環。設p=0;q=q-p;再進過i(i>=0)步後，p=(p+i)%m；q=(q+2*i)%m；則必存在一個i使得(p+i)%m = (q+2*i)%m。(p,q 都為常數)。
二、找到環的入口點
當fast若與slow相遇時，slow肯定沒有走周遊完連結清單，而fast已經在環内循環了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數還等于s 加上在環上多轉的n圈），設環長為r，則：2s = s + nrs= nr設整個連結清單長L，入口環與相遇點距離為x，起點到環入口點的距離為a。a + x = nra + x = (n – 1)r +r = (n-1)r + L - aa = (n-1)r + (L – a – x)(L – a – x)為相遇點到環入口點的距離，由此可知，從連結清單頭到環入口點等于(n-1)循環内環+相遇點到環入口點，于是我們從連結清單頭、與相遇點分别設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。程式描述如下
slist* FindLoopPort(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break;
}
if (fast == NULL || fast->next == NULL)
return NULL;
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
擴充問題：判斷兩個單連結清單是否相交，如果相交，給出相交的第一個點（兩個連結清單都不存在環）。
比較好的方法有兩個：
一、将其中一個連結清單首尾相連，檢測另外一個連結清單是否存在環，如果存在，則兩個連結清單相交，而檢測出來的依賴環入口即為相交的第一個點。
3，BITMAP
一、bitmap算法思想
32位機器上，一個整形，比如int a; 在記憶體中占32bit位，可以用對應的32bit位對應十進制的0-31個數，bitmap算法利用這種思想處理大量資料的排序與查詢.
優點：1.運算效率高，不許進行比較和移位；2.占用記憶體少，比如N=10000000；隻需占用記憶體為N/8=1250000Byte=1.25M。
缺點：所有的資料不能重複。即不可對重複的資料進行排序和查找。
比如：
第一個4就是
00000000000000000000000000010000
而輸入2的時候
00000000000000000000000000010100
輸入3時候
00000000000000000000000000011100
輸入1的時候
00000000000000000000000000011110
思想比較簡單，關鍵是十進制和二進制bit位需要一個map圖，把十進制的數映射到bit位。下面詳細說明這個map映射表。
二、map映射表
假設需要排序或者查找的總數N=10000000，那麼我們需要申請記憶體空間的大小為int a[1 + N/32]，其中：a[0]在記憶體中占32為可以對應十進制數0-31，依次類推：
bitmap表為：
a[0]--------->0-31
a[1]--------->32-63
a[2]--------->64-95
a[3]--------->96-127
..........
那麼十進制數如何轉換為對應的bit位，下面介紹用位移将十進制數轉換為對應的bit位。
三、位移轉換
例如十進制0，對應在a[0]所占的bit為中的第一位：
00000000000000000000000000000001
0-31：對應在a[0]中
i =0 00000000000000000000000000000000
temp=0 00000000000000000000000000000000
answer=1 00000000000000000000000000000001
i =1 00000000000000000000000000000001
temp=1 00000000000000000000000000000001
answer=2 00000000000000000000000000000010
i =2 00000000000000000000000000000010
temp=2 00000000000000000000000000000010
answer=4 00000000000000000000000000000100
i =30 00000000000000000000000000011110
temp=30 00000000000000000000000000011110
answer=1073741824 01000000000000000000000000000000
i =31 00000000000000000000000000011111
temp=31 00000000000000000000000000011111
answer=-2147483648 10000000000000000000000000000000
32-63：對應在a[1]中
i =32 00000000000000000000000000100000
temp=0 00000000000000000000000000000000
answer=1 00000000000000000000000000000001
i =33 00000000000000000000000000100001
temp=1 00000000000000000000000000000001
answer=2 00000000000000000000000000000010
i =34 00000000000000000000000000100010
temp=2 00000000000000000000000000000010
answer=4 00000000000000000000000000000100
i =61 00000000000000000000000000111101
temp=29 00000000000000000000000000011101
answer=536870912 00100000000000000000000000000000
i =62 00000000000000000000000000111110
temp=30 00000000000000000000000000011110
answer=1073741824 01000000000000000000000000000000
i =63 00000000000000000000000000111111
temp=31 00000000000000000000000000011111
answer=-2147483648 10000000000000000000000000000000
淺析上面的對應表：
1.求十進制0-N對應在數組a中的下标：
十進制0-31，對應在a[0]中，先由十進制數n轉換為與32的餘可轉化為對應在數組a中的下标。比如n=24,那麼 n/32=0，則24對應在數組a中的下标為0。又比如n=60,那麼n/32=1，則60對應在數組a中的下标為1，同理可以計算0-N在數組a中的下标。
2.求0-N對應0-31中的數：
十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得對應0-31中的數。
3.利用移位0-31使得對應32bit位為1.
四、程式設計實作
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];//申請記憶體的大小
//set 設定所在的bit位為1
//clr 初始化所有的bit位為0
//test 測試所在的bit為是否為1
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main()
{ int i;
for (i = 0; i < N; i++)
clr(i);
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}
解析本例中的void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
1.i>>SHIFT：
其中SHIFT=5，即i右移5為，2^5=32,相當于i/32，即求出十進制i對應在數組a中的下标。比如i=20，通過i>>SHIFT=20>>5=0 可求得i=20的下标為0；
2.i & MASK：
其中MASK=0X1F,十六進制轉化為十進制為31，二進制為0001 1111，i&（0001 1111）相當于保留i的後5位。
比如i=23，二進制為：0001 0111，那麼
0001 0111
& 0001 1111 = 0001 0111 十進制為：23
比如i=83，二進制為：0000 0000 0101 0011，那麼
0000 0000 0101 0011
& 0000 0000 0001 0000 = 0000 0000 0001 0011 十進制為：19
i & MASK相當于i%32。
3.1<<(i & MASK)
相當于把1左移 (i & MASK)位。
比如(i & MASK)=20，那麼i<<20就相當于：
0000 0000 0000 0000 0000 0000 0000 0001 >>20
=0000 0000 0000 1000 0000 0000 0000 0000
4.void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }等價于：
void set(int i)
{
a[i/32] |= (1<<(i%32));
}
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)