面試題目:反轉連結串列的演算法實現
連結串列通常有單鏈表,雙鏈表和迴圈連結串列,是面試裡面常涉及到的考點。連結串列的結構簡單,但是涉及到指標的操作,容易出現新的理解,其中也牽涉到許多小的細節的考慮。
面試題:反轉連結串列
題目描述:定義一個函式,輸入一個連結串列的頭結點,求反轉後該連結串列的輸出和連結串列的頭結點。
連結串列結點定義如下:
1 struct ListNode { 2int val; 3struct ListNode *next; 4ListNode(int x) : 5val(x), next(NULL) {//建構函式 6} 7 };
分析:
連結串列前後元素的關聯就是通過指標實現的,每個連結串列都有一個next指標指向下一個結點,末尾的節點的next域則置NULL;
反轉連結串列就是要求修改指標的指向。下面的圖就是反轉前和反轉後的效果。
反轉前:
反轉後:
下面來實現如何對連結串列進行反轉。
假設我們現在正在對結點3進行反轉操作,即原來結點2的next域指向j結點3(圖中已經調整完畢,現在指向前一個結點),結點3的next域指向結點4。現在要做的是將結點3的next域指向結點2。從圖中我們可以看出,當把結點3的next指標指向結點2的同時,原先指向的4就已經無法被正常的訪問到了,為了避免“斷鏈”,我們必須在指標更改指向之前,儲存修改結點的下一結點。同時我們也必須儲存上一個結點,因為next域即將修改指向該結點。因此定義三個指標,分別指向當前遍歷的結點,前一個結點和後一個結點。
演算法實現如下:
1 ListNode* ReverseList(ListNode* pHead) 2 { 3ListNode* pReversedHead = NULL; 4ListNode* pNode = pHead; 5ListNode* pPrev = NULL; 6while(pNode != NULL) 7{ 8ListNode* pNext = pNode->next; 9 10if(pNext == NULL) 11pReversedHead = pNode; 12 13pNode->next = pPrev; 14 15pPrev = pNode; 16pNode = pNext; 17} 18 19return pReversedHead; 20 }
當然使用下面這樣想法也是可以的,兩者的思路一致,沒有差別。只不過下面的程式碼必須注意一點,跳出while迴圈的時候,最後一個結點的next域指向前一個結點,否則就會導致“斷鏈”。
1ListNode* ReverseList(ListNode* pHead) { 2ListNode *base=pHead; 3ListNode *pre=NULL; 4ListNode *pnext=NULL; 5if(pHead==NULL) return NULL; 6while(base->next){ 7pnext=base->next; 8base->next=pre; 9pre=base; 10base=pnext; 11} 12base->next=pre; 13return base; 14}