第C++進(jìn)階練習(xí)刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)詳解目錄1.鏈接2.題目描述3.解題思路4.題解

1.鏈接

19.刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn).

2.題目描述

3.解題思路

方法一

1.在對(duì)鏈表進(jìn)行操作時(shí)，一種常用的技巧是添加一個(gè)啞節(jié)點(diǎn)（dummynode），它的next指針指向鏈表的頭節(jié)點(diǎn)。這樣一來，我們就不需要對(duì)頭節(jié)點(diǎn)進(jìn)行特殊的判斷了。

例如，在本題中，如果我們要?jiǎng)h除節(jié)點(diǎn)y，我們需要知道節(jié)點(diǎn)y的前驅(qū)節(jié)點(diǎn)x，并將x的指針指向y的后繼節(jié)點(diǎn)。

但由于頭節(jié)點(diǎn)不存在前驅(qū)節(jié)點(diǎn)，因此我們需要在刪除頭節(jié)點(diǎn)時(shí)進(jìn)行特殊判斷。但如果我們添加了啞節(jié)點(diǎn)，那么頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是啞節(jié)點(diǎn)本身，此時(shí)我們就只需要考慮通用的情況即可。特別地，在某些語言中，由于需要自行對(duì)內(nèi)存進(jìn)行管理。因此在實(shí)際的面試中，對(duì)于「是否需要釋放被刪除節(jié)點(diǎn)對(duì)應(yīng)的空間」這一問題，我們需要和面試官進(jìn)行積極的溝通以達(dá)成一致。下面的代碼中默認(rèn)不釋放空間。

一種容易想到的方法是，我們首先從頭節(jié)點(diǎn)開始對(duì)鏈表進(jìn)行一次遍歷，得到鏈表的長(zhǎng)度L。隨后我們?cè)購念^節(jié)點(diǎn)開始對(duì)鏈表進(jìn)行一次遍歷，當(dāng)遍歷到第Ln+1個(gè)節(jié)點(diǎn)時(shí)，它就是我們需要?jiǎng)h除的節(jié)點(diǎn)。為了方便刪除操作，我們可以從啞節(jié)點(diǎn)開始遍歷Ln+1個(gè)節(jié)點(diǎn)。當(dāng)遍歷到第Ln+1個(gè)節(jié)點(diǎn)時(shí)，它的下一個(gè)節(jié)點(diǎn)就是我們需要?jiǎng)h除的節(jié)點(diǎn)，這樣我們只需要修改一次指針，就能完成刪除操作。

方法二

我們可以設(shè)想假設(shè)設(shè)定了雙指針p和q的話，當(dāng)q指向末尾的NULL，p與q之間相隔的元素個(gè)數(shù)為n時(shí)，那么刪除掉p的下一個(gè)指針就完成了要求。

設(shè)置虛擬節(jié)點(diǎn)dummyHead指向head

設(shè)定雙指針p和q，初始都指向虛擬節(jié)點(diǎn)dummyHead

移動(dòng)q，直到p與q之間相隔的元素個(gè)數(shù)為n

同時(shí)移動(dòng)p與q，直到q指向的為NULL

將p的下一個(gè)節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)

4.題解

方法一

/**

*Definitionforsingly-linkedlist.

*structListNode{

*intval;

*ListNode*next;

*ListNode():val(0),next(nullptr){}

*ListNode(intx):val(x),next(nullptr){}

*ListNode(intx,ListNode*next):val(x),next(next){}

*};

classSolution{

public:

intgetLength(ListNode*head){

intlength=0;

while(head){

++length;

head=head-next;

returnlength;

ListNode*removeNthFromEnd(ListNode*head,intn){

ListNode*dummy=newListNode(0,head);

intlength=getLength(head);

ListNode*cur=dummy;

for(inti=1;ilength-n+1;++i){

cur=cur-next;

cur-next=cur-next-next;

ListNode*ans=dummy-next;

deletedummy;

returnans;

};

方法二

/**

*Definitionforsingly-linkedlist.

*structListNode{

*intval;

*ListNode*next;

*ListNode():val(0),next(nullptr){}

*ListNode(intx):val(x),next(nullptr){}

*ListNode(intx,ListNode*next):val(x),next(next){}

*};

classSolution{

public:

ListNode*removeNthFromEnd(ListNode*head,intn){

ListNode*dummyHead=newListNode(0);

dummyHead-next=head;

ListNode*p=dummyHead;

ListNode*q=dummyHead;

for(inti=0;in+1;i++){

q=q-next;

while(q){

p=p-next;

q=q-next;

ListNode*delNode=p-next;

p-nex