本节重点:虚拟头节点
小重点:设计链表,比较新颖的题型
一、[203]移除链表元素
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummyHead=new ListNode(0);dummyHead.next=head;ListNode pre=dummyHead;while(pre.next!=null){if(pre.next.val!=val){pre=pre.next;}else{pre.next=pre.next.next;}}return dummyHead.next;}
}
二、[707]设计链表
重点:定义size!!!,并在添加时,删除时改变size大小
class MyLinkedList {int size;ListNode dummyHead;public MyLinkedList() {size=0;dummyHead=new ListNode(-1);}public int get(int index) {if(index<0||index>=size){return -1;}ListNode cur=dummyHead;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);}public void addAtIndex(int index, int val) {if(index<0){index=0;}if(index>size){return;}ListNode pre=dummyHead;for(int i=0;i<index;i++){pre=pre.next;}ListNode toAdd=new ListNode(val);toAdd.next=pre.next;pre.next=toAdd;size++;}public void deleteAtIndex(int index) {if(index<0||index>=size) {return;}//注意size--;ListNode pre=dummyHead;for(int i=0;i<index;i++){pre=pre.next;}pre.next=pre.next.next;}
}
三、[206]反转链表
重点:理解逻辑,找对方法!!!
class Solution {public ListNode reverseList(ListNode head) {ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode tmp=cur.next;cur.next=pre;pre=cur;cur=tmp;}return pre;}
}