● 請(qǐng)你說出幾種基本的數(shù)據(jù)結(jié)構(gòu)，

參考回答：

常見的基本的數(shù)據(jù)結(jié)構(gòu)有鏈表、棧、隊(duì)列、樹(只列出面試常考的基本數(shù)據(jù)結(jié)構(gòu))

1、鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列節(jié)點(diǎn)組成，這些節(jié)點(diǎn)不必在內(nèi)存中相連。每個(gè)節(jié)點(diǎn)由數(shù)據(jù)部分Data和鏈部分Next，Next指向下一個(gè)節(jié)點(diǎn)，這樣當(dāng)添加或者刪除時(shí)，只需要改變相關(guān)節(jié)點(diǎn)的Next的指向，效率很高。

棧和隊(duì)列是比較特殊的線性表

棧是限制插入和刪除只能在一個(gè)位置上進(jìn)行的表，后進(jìn)先出

隊(duì)列只允許在front端進(jìn)行刪除操作，在rear端進(jìn)行插入操作，

樹：樹型結(jié)構(gòu)是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，考察主要以二叉樹為主，

● 手寫代碼：怎么判斷鏈表有環(huán)，怎么找環(huán)節(jié)點(diǎn)

參考回答：

判斷是否有環(huán)以及環(huán)節(jié)點(diǎn)

public?class?Solution?{ListNode?EntryNodeOfLoop(ListNode?h){if(h?==?null?||?h.next?==?null)return?null;ListNode?slow?=?h;ListNode?fast?=?h;while(fast?!=?null?&&?fast.next?!=?null?){slow?=?slow.next;fast?=?fast.next.next;if(slow?==?fast){ListNode?p=h;

ListNode q=slow;//相當(dāng)于讓q指向了m1

復(fù)制代碼1

2

3

4

5

6

7

8

9

10while(p != q){

p = p.next;

q = q.next;

}

if(p == q)

return?q;

}

}

return?null;

}

● 手寫代碼：一個(gè)單向鏈表，給出頭結(jié)點(diǎn)，找出倒數(shù)第N個(gè)結(jié)點(diǎn)，要求O(N)的時(shí)間復(fù)雜度；

參考回答：

JAVA版本：

public?class?Solution?{public?ListNode?FindNthToTail(ListNode?head,int?N)?{ListNode?pre=null,p=null;

//兩個(gè)指針都指向頭結(jié)點(diǎn)

p=head;

pre=head;

//記錄N值

int a=N;

//記錄節(jié)點(diǎn)的個(gè)數(shù)

int count=0;

//p指針先跑，并且記錄節(jié)點(diǎn)數(shù)，當(dāng)p指針跑了N-1個(gè)節(jié)點(diǎn)后，pre指針開始跑，

//當(dāng)p指針跑到最后時(shí)，pre所指指針就是倒數(shù)第N個(gè)節(jié)點(diǎn)

while(p!=null){p=p.next;count++;if(N<1){pre=pre.next;}N--;}

//如果節(jié)點(diǎn)個(gè)數(shù)小于所求的倒數(shù)第N個(gè)節(jié)點(diǎn)，則返回空

if(count

C/C++版本：

復(fù)制代碼1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32class?Solution {

public:

ListNode* FindNthToTail(ListNode* pListHead, unsignedint?N) {

if(pListHead==NULL||N==0)

return?NULL;

ListNode*pTail=pListHead,*pHead=pListHead;

for(int?i=1;i

{

if(pHead->next!=NULL)

pHead=pHead->next;

else

return?NULL;

}

while(pHead->next!=NULL)

{

pHead=pHead->next;

pTail=pTail->next;

}

return?pTail;

}

};

Python：

class?Solution:

def FindNthToTail(self, head, N):

# write code here

res=[]

while?head:

res.append(head)

head=head.next

if?N>len(res) or N<1:

return

return?res[-N]

● 請(qǐng)問如何判斷一個(gè)單向鏈表存在回路？

參考回答：

方法1：用一個(gè)指針數(shù)組A，存儲(chǔ)已訪問過的節(jié)點(diǎn)。用一個(gè)指針p，每次在鏈表上移動(dòng)一步，然后與指針數(shù)組A比較，若數(shù)組中沒有指針與p相同，說明第一次訪問p，將p放入數(shù)組中；若有指針與p相同，則存在環(huán)路，且第一次相同的節(jié)點(diǎn)就是環(huán)的入口點(diǎn)。

鏈表長度為n，則需要空間o(n)，且每次要與指針數(shù)組比較，時(shí)間復(fù)雜度為 O(n^2)。

方法2：在節(jié)點(diǎn)上記錄該節(jié)點(diǎn)是否被訪問過，如果在指針移動(dòng)過程中遇到已訪問過的節(jié)點(diǎn)，說明存在環(huán)路。同樣地，第一次相同的節(jié)點(diǎn)就是環(huán)的入口點(diǎn)。

方法3：用兩個(gè)指針，pSlow，pFast，一個(gè)慢一個(gè)快，慢的一次跳一步，，快的一次跳兩步，如果快的能追上慢的就表示有環(huán)(pSlow == pFast )。

● 請(qǐng)問如何判斷一個(gè)鏈表是否有環(huán)

參考回答：

方法1：用一個(gè)指針數(shù)組A，存儲(chǔ)已訪問過的節(jié)點(diǎn)。用一個(gè)指針p，每次在鏈表上移動(dòng)一步，然后與指針數(shù)組A比較，若數(shù)組中沒有指針與p相同，說明第一次訪問p，將p放入數(shù)組中；若有指針與p相同，則存在環(huán)路，且第一次相同的節(jié)點(diǎn)就是環(huán)的入口點(diǎn)。

鏈表長度為n，則需要空間o(n)，且每次要與指針數(shù)組比較，時(shí)間復(fù)雜度為 O(n^2)。

方法2：在節(jié)點(diǎn)上記錄該節(jié)點(diǎn)是否被訪問過，如果在指針移動(dòng)過程中遇到已訪問過的節(jié)點(diǎn)，說明存在環(huán)路。同樣地，第一次相同的節(jié)點(diǎn)就是環(huán)的入口點(diǎn)。

方法3：用兩個(gè)指針，pSlow，pFast，一個(gè)慢一個(gè)快，慢的一次跳一步，，快的一次跳兩步，如果快的能追上慢的就表示有環(huán)(pSlow == pFast )。

● 請(qǐng)問如何判斷兩個(gè)鏈表是否相交

參考回答：

從頭遍歷兩個(gè)鏈表。創(chuàng)建兩個(gè)棧，第一個(gè)棧存儲(chǔ)第一個(gè)鏈表的節(jié)點(diǎn)，第二個(gè)棧存儲(chǔ)第二個(gè)鏈表的節(jié)點(diǎn)。每遍歷到一個(gè)節(jié)點(diǎn)時(shí)，就將該節(jié)點(diǎn)入棧。兩個(gè)鏈表都入棧結(jié)束后。則通過top判斷棧頂?shù)墓?jié)點(diǎn)是否相等即可判斷兩個(gè)單鏈表是否相交。因?yàn)槲覀冎?#xff0c;若兩個(gè)鏈表相交，則從第一個(gè)相交節(jié)點(diǎn)開始，后面的節(jié)點(diǎn)都相交。若兩鏈表相交，則循環(huán)出棧，直到遇到兩個(gè)出棧的節(jié)點(diǎn)不相同，則這個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)就是第一個(gè)相交的節(jié)點(diǎn)。

node temp=NULL; //存第一個(gè)相交節(jié)點(diǎn)

while(!stack1.empty()&&!stack1.empty()) //兩棧不為空

復(fù)制代碼1

2

3

4

5

6

7

8

9{

temp=stack1.top();

stack1.pop();

stack2.pop();

if(stack1.top()!=stack2.top())

{

break;

}

}

● 手寫代碼：循環(huán)鏈表插入元素

參考回答：

typedef?struct?_tag_CircleListNode{struct?_tag_CircleListNode?*?next;}CircleListNode;typedef?struct?_tag_CircleList{CircleListNode?header;CircleListNode*?slider;int?length;}TCircleList;

//插入元素

int?CircleList_insert(CircleList*?list,?CireListNode*?node,?int?pos){int?ret?=?0,?i=0;TCircleList*?sList?=?(TCircleList*)list;if?(list?==?NULL?||?node==?NULL?||?pos<0){return?-1;}CircleListNode*?current?=?(CircleListNode*)sList;for(i=0;?(inext?!=?NULL);?i++){current?=?current->next;}

//current->next 0號(hào)節(jié)點(diǎn)的地址

復(fù)制代碼1

2node->next = current->next; //1

current->next = node; //2

//若第一次插入節(jié)點(diǎn)

if(?sList->length?==?0?){sList->slider?=?node;}sList->length++;

//若頭插法 current仍然指向頭部

//(原因是：跳0步，沒有跳走) 中間第一種情況

復(fù)制代碼1

2if( current == (CircleListNode*)sList )

{

//獲取最后一個(gè)元素

復(fù)制代碼1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24CircleListNode* last = CircleList_Get(sList, sList->length - 1);

last->next = current->next;//3

}

return?ret;

}

CircleListNode* CircleList_Get(CircleList* list,int?pos)// O(n)

{

TCircleList* sList = (TCircleList*)list;

CircleListNode* ret = NULL;

int?i = 0;

if?(list==NULL || pos<0)

{

return?NULL;

}

{

CircleListNode* current = (CircleListNode*)sList;

for(i=0; i

{

current = current->next;

}

ret = current->next;

}

return?ret;

}

總結(jié)

以上是生活随笔為你收集整理的python 单链表是否有回路_第5章 第1节 链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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