重庆网站建设外包公司,泉州企业制作网站,织梦如何将wordpress,汕头网络推广JAVA代码编写
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。
示例 1#xff1a; 输入#xff1a;head [1,2,6,3,4,5,6], val 6
输出#xff1a;[1,2,3,4,5]示…JAVA代码编写
203. 移除链表元素
给你一个链表的头节点 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
输出[]提示
列表中的节点数目在范围 [0, 104] 内1 Node.val 500 val 50
教程https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
视频https://www.bilibili.com/video/BV18B4y1s7R9
方法一设置一个虚拟头结点
思路首先为什么要加虚拟头结点是因为如果要删的元素是头结点会与删后面的结点操作不一样这样比较方便。定义一个当前指针cur用来变量定义一个pre指针用来删除结点经典的指针删除的操作如下图所示将pre指向cur。这里要注意的是当不是要删除的元素时pre指针需要往后移一位。还有while循环需要注意虽然看代码能懂写起来还是有点磕磕绊绊。 复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
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 (headnull){//如果头结点head为空return head;//直接返回head不需要删除操作}ListNode dummynew ListNode(-1,head);//定义一个指针值为-1在head前一个ListNode pre dummy;//当前指针的前一个指针ListNode cur head;//当前指针while(cur!null){//当前指针不为空if (cur.valval){//指针值是目标值pre.nextcur.next;//前一个指针直接指向下下个指针跳过指定目标值}else {pre cur;//如果不是要删除的指针就和cur一样往后移一位以便下一次删除操作}curcur.next;}return dummy.next;}}看一个例子输入head [1,2,6,3,4,5,6], 要删元素6。
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummyHead new ListNode(0);dummyHead.next head;//在head之前定义一个dummyHead结点其值为0ListNode temp dummyHead;while (temp.next ! null) {if (temp.next.val val) {temp.next temp.next.next;} else {temp temp.next;}}return dummyHead.next;}
}这个代码是leetcode官方提供的与卡哥的代码差不多这里少定义了一个指针cur因为curtemp.next这里都用temp代劳了。
707. 设计链表
企业谷歌、亚马逊、字节
你可以选择使用单链表或者双链表设计并实现自己的链表。
单链表中的节点应该具备两个属性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提示
0 index, val 1000请不要使用内置的 LinkedList 库。调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。
教程https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频https://www.bilibili.com/video/BV1FU4y1X7WD
方法一单链表
思路
复杂度分析 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1) 空间复杂度: O(n)
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.valval;}
}
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;//包含一个虚拟头节点所以查找第 index1 个节点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;}
}206. 反转链表
微软 Microsoft、亚马逊、奥多比 Adobe
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3
输入head []
输出[]提示
链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000
**进阶**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
教程https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
视频https://www.bilibili.com/video/BV1nB4y1i7eL
方法一双指针法
思路
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
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 null;while(cur!null){temp cur.next;cur.nextpre;后一个指针指向前一个指针precur;curtemp;}return pre;}
}
