数组理论基础
文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
203.移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，
但是要注意删除头结点的情况。
思路1:使用虚拟头结点
设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 方法1：添加虚拟结点
ListNode dummy = new ListNode(0,head);
ListNode pre = dummy;
while(pre.next != null){
if(pre.next.val == val){
pre.next = pre.next.next;
}else {
pre = pre.next;
}
}
return dummy.next;
}
}
思路2:不使用虚拟头结点
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 方法2：不添加虚拟头结点
// 要特殊判断
while(head!=null && head.val==val)
head = head.next;
// 此时可能是空节点,如果不加判断的话,后面cur.next就可能报错
if(head==null) return head;
ListNode cur = head;
while(cur.next!=null){
if(cur.next.val==val)
{
cur.next = cur.next.next;
}
else{
cur = cur.next;
}
}
return head;
}
}
时间复杂度 O(n)
707.设计链表
题目连接：https://leetcode.cn/problems/design-linked-list/
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
解法：使用虚拟头结点（这样会方便一点）
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 MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
this.size = 0;
// 虚拟头节点
head = new ListNode(0);
}
public int get(int index) {
if(index<0 || index>=size)
return -1;
ListNode cur = head.next;
for(int i=0;i<index;i++)
{
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
// addAtIndex(0,val);
ListNode cur = head;
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next = newNode;
size++;
}
public void addAtTail(int val) {
// addAtIndex(size,val);
ListNode cur = head;
ListNode newNode = new ListNode(val);
for(int i=0;i<size;i++)
cur = cur.next;
newNode.next = cur.next;
cur.next = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if(index > size || index <0)
return;
// 定位到插入的结点
ListNode cur = head;
for(int i = 0;i<index;i++){
cur = cur.next;
}
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if(index >= size || index <0)
return;
// 定位到删除的结点
ListNode cur = head;
for(int i = 0;i<index;i++){
cur = cur.next;
}
cur.next = cur.next.next;
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);
*/
时间复杂度O(n)
206.反转链表
题目连接：https://leetcode.cn/problems/reverse-linked-list/
解法：改变指针的指向
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变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 reverseList(ListNode head) {
ListNode cur = head;
ListNode pre=null, tmp=null;
while(cur!=null){
tmp = cur.next; // 2
cur.next = pre; // 1 -> null
pre = cur; // pre = 1
cur = tmp;
}
return pre;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
