(題目來源:力扣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;
????}
}