203.移除链表元素
建议: 本题最关键是要理解 虚拟头结点的使用技巧,这个对链表题目很重要。
题目链接/文章讲解/视频讲解::代码随想录
思路
需要注意将cur = cur.next;放在else中。因为涉及到删除会指向next.next,再向前会涉及到空指针异常
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = new ListNode();
cur = dummy;
if(head==null){
return null;
}
while(cur.next!=null){
if(cur.next.val == val){
cur.next= cur.next.next;
}
else
cur = cur.next;
}
return dummy.next;
}
}
707.设计链表
建议: 这是一道考察 链表综合操作的题目,不算容易,可以练一练 使用虚拟头结点
题目链接/文章讲解/视频讲解:代码随想录
class MyLinkedList {
int size;
ListNode dummy = new ListNode(0);
public MyLinkedList() {
size = 0;
}
public int get(int index) {
if(index<0||index>=size){
return -1;
}
ListNode cur = dummy;
if(cur!=null){
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
ListNode temp = new ListNode(val);
temp.next = dummy.next;
dummy.next = temp;
size++;
}
public void addAtTail(int val) {
ListNode cur = dummy;
while(cur.next!=null){
cur = cur.next;
}
cur.next = new ListNode(val);
size++;
}
public void addAtIndex(int index, int val) {
ListNode cur = dummy;
if(index<0||index>size){
} else if (index==size) {
addAtTail(val);
} else {
while(index>0){
cur = cur.next;
index--;
}
ListNode temp = new ListNode(val);
temp.next = cur.next;
cur.next = temp;
size++;
}
}
public void deleteAtIndex(int index) {
ListNode cur = dummy;
if(index<0||index>=size){
}
else {
while(index>0){
cur = cur.next;
index--;
}
if(cur.next!=null&&cur.next.next!=null)
cur.next = cur.next.next;
else cur.next = null;
size--;
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
206.反转链表
建议先看我的视频讲解,视频讲解中对 反转链表需要注意的点讲的很清晰了,看完之后大家的疑惑基本都解决了。
题目链接/文章讲解/视频讲解:代码随想录
思路
双指针法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode tmp ;
while(cur!=null){
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}