C++進階練習刪除鏈表的倒數(shù)第N個結(jié)點詳解

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

1.鏈接

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

2.題目描述

3.解題思路

方法一

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

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

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

一種容易想到的方法是，我們首先從頭節(jié)點開始對鏈表進行一次遍歷，得到鏈表的長度L。隨后我們再從頭節(jié)點開始對鏈表進行一次遍歷，當遍歷到第Ln+1個節(jié)點時，它就是我們需要刪除的節(jié)點。為了方便刪除操作，我們可以從啞節(jié)點開始遍歷Ln+1個節(jié)點。當遍歷到第Ln+1個節(jié)點時，它的下一個節(jié)點就是我們需要刪除的節(jié)點，這樣我們只需要修改一次指針，就能完成刪除操作。

方法二

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

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

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

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

同時移動p與q，直到q指向的為NULL

將p的下一個節(jié)點指向下下個節(jié)點

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