一、今日刷题
1. 第五部分：链表 -- 203.移除链表元素2. 第五部分：链表 -- 707.设计链表 二、知识积累
1.什么是链表？2.链表的类型：
①单链表：②双链表：③循环链表： 3.链表的Java实现：4.链表与数组：
一、今日刷题 1. 第五部分：链表 – 203.移除链表元素
跳转LeetCode
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
答案代码：
用迭代的方法删除链表中所有节点值等于特定值的节点。
用 temp 表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：
temp.next = temp.next.next
如果 temp 的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 temp 移动到下一个节点即可。
当 temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 val 的节点都被删除。
具体实现方面，由于链表的头节点 head 有可能需要被删除，因此创建哑节点dummyHead，令 dummyHead.next =head，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。
package linkedList;
public class RemoveElements {
public static void main(String[] args) {
RemoveElements removeElements = new RemoveElements();
//构造链表head并输出，但发现while循环输出后，链表head变为null了，无法再执行removeElements方法
//所以将此处仅用于测试创建链表以及输出链表的head更名为headTest
ListNode headTest = new ListNode(1);
headTest.next = new ListNode(2);
headTest.next.next = new ListNode(6);
System.out.println(headTest);
while (headTest != null) {
System.out.println(headTest.val);
headTest = headTest.next;
}
System.out.println("*************************");
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(6);
ListNode ans = removeElements.removeElements(head, 6);
while (ans != null) {
System.out.println(ans.val);
ans = ans.next;
}
}
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode tmp = dummyHead;
while (tmp.next != null) {
if (tmp.next.val == val) {
tmp.next = tmp.next.next;
} else {
tmp = tmp.next;
}
}
return dummyHead.next;
}
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
2. 第五部分：链表 – 707.设计链表
跳转LeetCode
答案代码：
package linkedList;
public class CreatlinkedList {
public static void main(String[] args) {
MylinkedList linkedList = new MylinkedList();
linkedList.addAtHead(1);
int num = linkedList.get(0);
System.out.println(num);
System.out.println("************************");
linkedList.addAtIndex(1, 6);
System.out.println(linkedList.get(1));
System.out.println("************************");
linkedList.deleteAtIndex(1);
System.out.println(linkedList.get(0));
}
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
static 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 tmp = head;
for (int i = 0; i < index + 1; i++) {
tmp = tmp.next;
}
return tmp.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 > size) return;
if (index < 0) index = 0;
size++;
ListNode pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
ListNode addNode = new ListNode(val);
addNode.next = pre.next;
pre.next = addNode;
}
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;
}
}
}
二、知识积累
参考来源
1.什么是链表？链表是一种通过指针串联在一起的线性结构，每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
2.链表的类型： ①单链表：单链表中的节点只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
链表首尾相连
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;
}
}
4.链表与数组：
数组是在内存中是连续分布的，但链表在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表是通过指针域的指针链接在内存中各个节点。
