C語言鍊錶類面試題

struct node

;建立單鏈表的程式為：

struct node* create(unsigned int n)

node* p = head;

for (unsigned int i = 1; i < n; i++)

return head;

}問題1：鍊錶逆置

思想為：head指標不斷後移，指標反向即可，**為：

void reverse(node*& head)

head->next = p;

}return;

}問題2：刪除不知頭結點鍊錶的某個節點

如果單向鍊錶不知道頭節點，乙個指標指向其中的乙個節點，問如何刪除這個指標指向的節點？

思想為：把這個節點的下乙個節點的值複製給該節點，然後刪除下乙個節點即可。

問題3：怎麼判斷鍊錶中是否有環？

思想為：設定兩個指標，乙個步長為1，另乙個步長為2，依次後移，如果相遇且都不為空，則有環。

與這個類似的問題包括：怎麼快速檢測出乙個巨大的鍊錶中的死鏈？或者如何找出乙個單鏈表的中間節點？

**為：

bool loop(node* head)

node* one = head;

node* two = head->next;

if (two == null)

while (one != two)

if (two != null)

if (two == null)

two = two->next;

if (one == null || two == null) }

if (one == null || two == null)

return flag;

}問題4：如果乙個單向鍊錶，其中有環，怎麼找出這個鍊錶迴圈部分的第乙個節點？

思想為：假設該節點在x位置處，假設步長為1的指標和步長為2的指標相遇在x+z處，迴圈的長度為y，那麼2(x+z)-(x+z)=k*y,

那麼當乙個指標再從開始出後移時，另乙個指標從相遇點開始後移時，這兩個指標就會在迴圈開始處相遇。

**為：

node* findloopplace(node* head, unsigned int* place = null)

node* one = head;

node* two = head->next;

unsigned int count = 1;

while (one != two)

one = head;

while (one != two)

two = two->next;

count++;

}*place = count;

return one;

}問題5：如何查詢鍊錶中倒數第k個節點？

思想為：兩個指向頭結點的指標，乙個先向後移動k位，然後兩個同時向後面移動直到乙個節點到達鏈尾，前面乙個指標的位置就是了。

node* findlastk(node* head,unsigned int k)

if (count < k)

p = head;

node* q = head;

for (unsigned int i = 0; i < k; i++)

while (p != null)

return q;

}問題6：程式設計序判斷兩個鍊錶是否相交。

這個問題的精彩解說請參見《程式設計之美》一書之《程式設計判斷兩個鍊錶是否相交》，這裡就不寫了，該書的pdf文件在網上很好下。

文章後面給了兩個擴充套件問題：

（1）如果鍊錶可能有環，如何做判斷？

思想為：首先應該明白，只有乙個鍊錶有環的情況下是不會相交的，只有都有環或者都沒有環的情況下才可能相交，都沒有環的情況下最簡便的方法就是判斷鏈尾是否相交即可；都有環的情況下，分別找到環上的任一點，乙個不動，另乙個步進，即可判斷是否相交。

（2）如何求相交鍊錶的第乙個節點？應該為單鏈表情況

思想為：方法一是先把任乙個鍊錶連成環，即從表尾接到表頭，按照問題4的解法；方法二是計算兩個鍊錶的長度，而兩個鍊錶是按照尾部對齊的，那麼從短鍊錶的第乙個位置從長鍊錶的第長度差+1的位置依次比較指標值，相等的位置即是。

相關程式包括：單鏈表中在某個位置插入環以及銷毀鍊錶等，**如下：

void insertcircle(node* head, unsigned int n)

if (n <= count)

p->next = q;

}return;

}void destroy(node* head)

head = head->next;

q->next = null;

destroy(head);

}else}}

C語言鍊錶類面試題

c語言面試題

C語言面試題

c語言面試題

C語言鍊錶類面試題

c語言面試題

C語言面試題

c語言面試題

相關推薦