目錄

?LeetCode203.移除鏈表元素?

?LeetCode707.設計鏈表??

?LeetCode206.反轉鏈表?

---

?LeetCode203.移除鏈表元素?

鏈接：203.移除鏈表元素

?我的做法是設置一個虛擬頭結點，因為頭結點的處理與其他節(jié)點不同，設置了虛擬頭結點，就可以把頭結點看成一個普通的節(jié)點，移除操作只用把前一個節(jié)點的next指向當前節(jié)點的next，代碼如下：

public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode dummy=new ListNode();dummy.next=head;ListNode pre=dummy;ListNode cur=head;while(cur!=null){if(cur.val==val){pre.next=cur.next;}else{pre=cur;}cur=cur.next;}return dummy.next;}

測試用例：

1.輸入一個含有值為val節(jié)點的鏈表

2.輸入一個不含值為val節(jié)點的鏈表

3.輸入一個只有值為val節(jié)點的鏈表

4.輸入的只有頭結點且值為val

5.輸入的只有頭結點且值不為val

6.輸入空鏈表

?LeetCode707.設計鏈表??

鏈接：707.設計鏈表

你可以選擇使用單鏈表或者雙鏈表，設計并實現(xiàn)自己的鏈表。

單鏈表中的節(jié)點應該具備兩個屬性：val?和?next?。val?是當前節(jié)點的值，next?是指向下一個節(jié)點的指針/引用。

如果是雙向鏈表，則還需要屬性?prev?以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(jié)點下標從?0?開始。

實現(xiàn)?MyLinkedList?類：

• MyLinkedList()?初始化?MyLinkedList?對象。
• int get(int index)?獲取鏈表中下標為?index?的節(jié)點的值。如果下標無效，則返回?-1?。
• void addAtHead(int val)?將一個值為?val?的節(jié)點插入到鏈表中第一個元素之前。在插入完成后，新節(jié)點會成為鏈表的第一個節(jié)點。
• void addAtTail(int val)?將一個值為?val?的節(jié)點追加到鏈表中作為鏈表的最后一個元素。
• void addAtIndex(int index, int val)?將一個值為?val?的節(jié)點插入到鏈表中下標為?index?的節(jié)點之前。如果?index?等于鏈表的長度，那么該節(jié)點會被追加到鏈表的末尾。如果?index?比長度更大，該節(jié)點將?不會插入?到鏈表中。
• void deleteAtIndex(int index)?如果下標有效，則刪除鏈表中下標為?index?的節(jié)點。

?

?

此題非?？简瀸︽湵淼牟僮?#xff0c;我做了蠻久的，也需要對鏈表有足夠的了解，本題做的時候也充分體現(xiàn)了虛擬頭結點的便利性，然后就是模擬鏈表的操作，以下是我的代碼：?

class ListNode{int val;ListNode next;ListNode(){};ListNode(int val){this.val=val;}
}
public class MyLinkedList {int size;   //鏈表長度ListNode head;  //虛擬頭結點// 初始化public MyLinkedList() {size=0;head=new ListNode();}// 獲取元素public int get(int index) {if(index<0 || index>=size){return -1;}ListNode cur=head;for(int i=0;i<=index;i++){cur=cur.next;}return cur.val;}// 頭插public void addAtHead(int val) {addAtIndex(0,val);}// 尾插public void addAtTail(int val) {addAtIndex(size,val);}// 插在index之前public void addAtIndex(int index, int val) {ListNode cur=head;if(index>size){return;}if(index<0){index=0;}for(int i=0;i<index;i++){cur=cur.next;}ListNode node=new ListNode(val);node.next=cur.next;cur.next=node;size++;}// 刪除Index位置上的元素public void deleteAtIndex(int index) {if(index<0 || index>=size){return;}
//        if(index==0){
//            head=head.next;
//        }ListNode cur=head;for(int i=0;i<index;i++){cur=cur.next;}cur.next=cur.next.next;size--;}
}

?LeetCode206.反轉鏈表?

鏈接：206.反轉鏈表

給你單鏈表的頭節(jié)點?head?，請你反轉鏈表，并返回反轉后的鏈表。

?

?之前寫過翻轉數(shù)組，是用雙指針解的，但是鏈表并不能直接獲取到某個節(jié)點，所以翻轉鏈表更考驗對鏈表的操作，寫鏈表題很容易就把自己繞進去，我建議可以在草稿紙上畫一下，這樣思路可以更清晰點（ps:我畫的太亂了，就不粘上來了），以下是我的代碼

public ListNode reverseList(ListNode head) {if(head==null || head.next==null){return head;}ListNode cur=head;ListNode pre=null;while(cur!=null){ListNode temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}

?測試用例：

1.輸入一個大于1個結點的鏈表

2.輸入一個只有一個節(jié)點的鏈表

3.輸入鏈表為空