騰訊的一道鏈表筆試題「總結」
- 總結
- 關注:1.16W次
出題的大致函數聲明:
node fun(node * head, int index),要我們實現函數裏面的方法。
其中node是一個單向鏈表。
要實現的`功能:返回倒數的第index個節點。
怎樣優化,看大家各自發揮~
對於這個問題屬於常見的問題了
一般設置兩個指針p1,p2
首先p1和p2都指向head
然後p2向前走n步,這樣p1和p2之間就間隔n個節點
然後p1和p2同時向前步進,當p2到達最後一個節點時,p1就是倒數第n個節點了
下面給出個例子來進一步説明
node fun(node * head, int index)
{
node *ptr1,*ptr2;
int i = 0;
ptr1 = head;
ptr2 = head;
if( head == NULL || head->next == NULL )
return ptr1;
while(i
ptr1 = ptr1->next;
if(ptr1 == NULL)
return head;
i++;
}
while(ptr1->next != NULL)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return *ptr2;
}
除了上面的方法,還有另外的方法,
一、整個static count 第一次遍歷時求出 鏈的總長,第二次開始直接步進count-index
缺點:進行了兩遍遍歷。
二、將鏈表倒置。其實也不是很好。
- 文章版權屬於文章作者所有,轉載請註明 https://xuewengu.com/flxz/zongjie/ojk93.html