本文主要是介绍Day3-链表第一部分|LeetCode203、707、206|代码随想录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天开始写链表的题目。链表的核心内容是需要了解它的一些基础是如何实现的，在此基础上做的延伸一般不会太复杂。
LeetCode 203 题目描述+解答
解题思路：移除链表中的元素，这里引入一个虚拟的头指针来统一操作。难度不大，主要是java基础不太好，自己写测试用例的时候耽误了很久。这里的判断，需要if else 本来写的时候没有带else，直接写的 cur=cur.next; 想着删除完了也得移动cur，就直接写了，但是这样会报错。因为如果当前val是对应到链表的最后一个元素，那我们的cur此时已经指向了null，下面如果再有一个cur=cur.next;语句，就会报错。所以这里要放在else中。
Java代码：
import org.joni.ast.ListNode;/*** 题目Id：203; * 题目：移除链表元素，remove-linked-list-elements; * 日期：2023-10-29 15:05:20
*///给你一个链表的头节点 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
//输出：[]/*** 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) {if (head == null) {return head;}ListNode dummy = new ListNode(-1,head);ListNode cur = dummy;while (cur.next != null){if (cur.next.val == val){cur.next=cur.next.next;}else{cur=cur.next;}}return dummy.next;}
}}
LeetCode 707 题目描述+解答
解题思路：这道题目有很多链表中涉及到的操作。是很基础且必须的题目。我写的太乱了，这里直接用网站上的代码做示例，有一个地方需要注意，就是链表中的size属性。
Java代码：
import com.github.weisj.jsvg.L;
import com.vladsch.flexmark.ast.LinkNode;
import com.vladsch.flexmark.util.sequence.BasedSequence;
import org.jetbrains.annotations.NotNull;/*** 题目Id：707; * 题目：设计链表，design-linked-list; * 日期：2023-10-29 16:00:04
*///你可以选择使用单链表或者双链表，设计并实现自己的链表。 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 // 实现 MyLinkedList 类：
// MyLinkedList() 初始化 MyLinkedList 对象。
// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
// void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果
//index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。 // 示例：
//输入
//["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get",
//"deleteAtIndex", "get"]
//[[], [1], [3], [1, 2], [1], [1], [1]]
//输出
//[null, null, null, null, 2, null, 3]
//
//解释
//MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.addAtHead(1);
//myLinkedList.addAtTail(3);
//myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
//myLinkedList.get(1); // 返回 2
//myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
//myLinkedList.get(1); // 返回 3//单链表
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.val=val;}
}
class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点public int get(int index) {//如果index非法，返回-1if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;//包含一个虚拟头节点，所以查找第 index+1 个节点for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点，等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度，则返回空public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;//找到要插入节点的前驱ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}//双链表
class ListNode{int val;ListNode next,prev;ListNode() {};ListNode(int val){this.val = val;}
}class MyLinkedList { //记录链表中元素的数量int size;//记录链表的虚拟头结点和尾结点ListNode head,tail;public MyLinkedList() {//初始化操作this.size = 0;this.head = new ListNode(0);this.tail = new ListNode(0);//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！head.next=tail;tail.prev=head;}public int get(int index) {//判断index是否有效if(index<0 || index>=size){return -1;}ListNode cur = this.head;//判断是哪一边遍历时间更短if(index >= size / 2){//tail开始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next; }}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(index>size){return;}//index小于0if(index<0){index = 0;}size++;//找到前驱ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建结点ListNode newNode = new ListNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(index<0 || index>=size){return;}//删除操作size--;ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}/*** 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);*/LeetCode 206 题目描述+解答
解题思路：链表反转问题。常规思路：利用双指针，只需要将现有链表的指针方向全部反过来就行了。递归思路：根据常规写法递归即可。
Java代码：
import org.joni.ast.ListNode;/*** 题目Id：206; * 题目：反转链表，reverse-linked-list; * 日期：2023-10-29 16:56:24
*///给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
// 示例 1：
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
//
// 示例 2：
//输入：head = [1,2]
//输出：[2,1]
//
// 示例 3：
//输入：head = []
//输出：[]/*** 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 pre = null;ListNode cur = head;ListNode temp = new ListNode();while (cur != null){temp = cur.next;cur.next = pre;pre=cur;cur=temp;}return pre;}
}
}//递归思路
class Solution {public ListNode reverse(ListNode cur,ListNode pre){ListNode temp = new ListNode();if (cur == null) return pre;//反转操作 递归的核心是抽象出来统一的操作，然后传不同的参数进去，找到核心操作步骤之后，理清楚要传的参数就能得到结果。temp = cur.next;cur.next = pre;return reverse(temp,cur);}public ListNode reverseList(ListNode head) {return reverse(head,null);}
}这篇关于Day3-链表第一部分|LeetCode203、707、206|代码随想录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
