一、今日刷题
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.链表与数组：
数组是在内存中是连续分布的，但链表在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表是通过指针域的指针链接在内存中各个节点。