設(shè)計(jì)鏈表

(題目來源:力扣LeetCode)

題目:設(shè)計(jì)鏈表的實(shí)現(xiàn)瞪慧。您可以選擇使用單鏈表或雙鏈表鸟廓。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性:val?和?next影暴。val?是當(dāng)前節(jié)點(diǎn)的值括改,next?是指向下一個(gè)節(jié)點(diǎn)的指針/引用腻豌。如果要使用雙向鏈表,則還需要一個(gè)屬性?prev?以指示鏈表中的上一個(gè)節(jié)點(diǎn)嘱能。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的吝梅。

在鏈表類中實(shí)現(xiàn)這些功能:

get(index):獲取鏈表中第?index?個(gè)節(jié)點(diǎn)的值。如果索引無效焰檩,則返回-1憔涉。

addAtHead(val):在鏈表的第一個(gè)元素之前添加一個(gè)值為?val?的節(jié)點(diǎn)订框。插入后析苫,新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。

addAtTail(val):將值為?val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。

addAtIndex(index,val):在鏈表中的第?index?個(gè)節(jié)點(diǎn)之前添加值為?val? 的節(jié)點(diǎn)衩侥。如果?index?等于鏈表的長度国旷,則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長度茫死,則不會(huì)插入節(jié)點(diǎn)跪但。如果index小于0,則在頭部插入節(jié)點(diǎn)峦萎。

deleteAtIndex(index):如果索引?index 有效屡久,則刪除鏈表中的第?index 個(gè)節(jié)點(diǎn)。


題解:

public?class?ListNode{

????int?val;

????ListNode?next;

????ListNode(int?x){

????????val?=?x;

????}

}

class?MyLinkedList?{

????int?size;

????ListNode?head;

????/**?Initialize?your?data?structure?here.?*/

????public?MyLinkedList()?{

????????size?=?0;

????????head?=?new?ListNode(0);

????}


????/**?Get?the?value?of?the?index-th?node?in?the?linked?list.?If?the?index?is?invalid,?return?-1.?*/

????public?int?get(int?index)?{

????????if(index<0?||?index>=size)?return?-1;

????????ListNode?cur?=?head;


????????????for(int?i=0;i<index+1;i++){

????????????????cur=?cur.next;

????????}

?????????return?cur.val;

????}


????/**?Add?a?node?of?value?val?before?the?first?element?of?the?linked?list.?After?the?insertion,?the?new?node?will?be?the?first?node?of?the?linked?list.?*/

????public?void?addAtHead(int?val)?{

????????addAtIndex(0,val);

????}


????/**?Append?a?node?of?value?val?to?the?last?element?of?the?linked?list.?*/

????public?void?addAtTail(int?val)?{

????????addAtIndex(size,val);

????}


????/**?Add?a?node?of?value?val?before?the?index-th?node?in?the?linked?list.?If?index?equals?to?the?length?of?linked?list,?the?node?will?be?appended?to?the?end?of?linked?list.?If?index?is?greater?than?the?length,?the?node?will?not?be?inserted.?*/

????public?void?addAtIndex(int?index,?int?val)?{

????????//如果索引大于長度

????????if(index>size)?return;

????????//如果索引小于0

????????if(index<0)

????????index=0;

????????//插入

????????++size;

????????ListNode?pre?=?head;

????????for(int?i?=0;i<index;++i)?pre?=?pre.next;

????????ListNode?toAdd?=?new?ListNode(val);

????????toAdd.next=pre.next;

????????pre.next=toAdd;



????}


????/**?Delete?the?index-th?node?in?the?linked?list,?if?the?index?is?valid.?*/

????public?void?deleteAtIndex(int?index)?{

????????if(index<0?||index>=size)?return;

????????size--;

????????ListNode?pre?=head;


????????????for(int?i=0;i<index;++i)?pre=pre.next;

????????????pre.next=pre.next.next;


????}

}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末爱榔,一起剝皮案震驚了整個(gè)濱河市被环,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌详幽,老刑警劉巖筛欢,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異唇聘,居然都是意外死亡版姑,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門迟郎,熙熙樓的掌柜王于貴愁眉苦臉地迎上來剥险,“玉大人,你說我怎么就攤上這事宪肖〕闯埃” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵匈庭,是天一觀的道長夫凸。 經(jīng)常有香客問我,道長阱持,這世上最難降的妖魔是什么夭拌? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮衷咽,結(jié)果婚禮上鸽扁,老公的妹妹穿的比我還像新娘。我一直安慰自己镶骗,他們只是感情好桶现,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著鼎姊,像睡著了一般骡和。 火紅的嫁衣襯著肌膚如雪相赁。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天慰于,我揣著相機(jī)與錄音钮科,去河邊找鬼。 笑死婆赠,一個(gè)胖子當(dāng)著我的面吹牛绵脯,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播休里,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼蛆挫,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了妙黍?” 一聲冷哼從身側(cè)響起璃吧,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎废境,沒想到半個(gè)月后畜挨,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡噩凹,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年巴元,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片驮宴。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡逮刨,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出堵泽,到底是詐尸還是另有隱情修己,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布迎罗,位于F島的核電站睬愤,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏纹安。R本人自食惡果不足惜尤辱,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望厢岂。 院中可真熱鬧光督,春花似錦、人聲如沸塔粒。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽卒茬。三九已至船老,卻和暖如春咖熟,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背努隙。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留辜昵,地道東北人荸镊。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像堪置,于是被迫代替她去往敵國和親躬存。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 【leetcode=鏈表】設(shè)計(jì)鏈表 題目: 設(shè)計(jì)鏈表的實(shí)現(xiàn)舀锨。您可以選擇使用單鏈表或雙鏈表岭洲。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩...
    程序員小2閱讀 216評(píng)論 0 1
  • 707 Design Linked List 設(shè)計(jì)鏈表 Description:Design your imple...
    air_melt閱讀 385評(píng)論 0 0
  • 題目 設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表坎匿。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性:val 和 next盾剩。val ...
    佟佳寧閱讀 136評(píng)論 0 0
  • 題目描述: 設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表替蔬。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性:val 和 next告私。v...
    華子24閱讀 260評(píng)論 0 0
  • 707. 設(shè)計(jì)鏈表 設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表承桥。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性:val 和 ne...
    TheKey_閱讀 224評(píng)論 0 0