网站开发肇庆培训,天眼网查询个人信息,义乌设计网站,天元建设集团有限公司简介203.移除链表元素
一遍AC
没什么难度#xff0c;记住如何定义、使用链表#xff0c;链表中的节点#xff1b;记住链表移除的操作代码#xff1b;了解虚拟头节点的用法#xff1b;
class Solution {public ListNode removeElements(ListNode head, int val) {if(head n…203.移除链表元素
一遍AC
没什么难度记住如何定义、使用链表链表中的节点记住链表移除的操作代码了解虚拟头节点的用法
class Solution {public ListNode removeElements(ListNode head, int val) {if(head null){return head;}ListNode dummyNode new ListNode(-1,head);ListNode currNode head;ListNode preNode dummyNode;while(currNode!null){if(currNode.val val){preNode.next currNode.next;}else{preNode currNode;}currNode currNode.next;}return dummyNode.next;}
}707.设计链表-单链表实现
重点 如何判断每个方法里面的for循环结束的条件如何判断index非法的条件
package LinkList;public class SingleLinkList {public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addAtHead(4);int first myLinkedList.get(1);myLinkedList.addAtHead(1);myLinkedList.addAtHead(5);myLinkedList.deleteAtIndex(3);myLinkedList.addAtHead(7);int second myLinkedList.get(3);int third myLinkedList.get(3);int fourth myLinkedList.get(3);myLinkedList.addAtHead(1);myLinkedList.deleteAtIndex(4);}
}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 dummy;public MyLinkedList() {size 0;dummy new ListNode(0);}public int get(int index) {/** 第一遍没有AC错误出在了这里* 一开始的条件是 index 0 || index size* 但是当测试用例为* myLinkedList.addAtHead(4);* int first myLinkedList.get(1);* 这时候size 1同时想要获取index1的元素其实是获取不到的* 但没有添加indexsize的非法条件* 就会导致return中的currNodenull* 因此currNode.val是非法的* */if (index 0 || index size) {return -1;}ListNode currNode dummy;for (int i 0; i index; i) {currNode currNode.next;}return currNode.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 0 || index size) {return;}ListNode addNode new ListNode(val);ListNode preNode dummy;for (int i 0; i index; i) {preNode preNode.next;}addNode.next preNode.next;preNode.next addNode;size;}public void deleteAtIndex(int index) {if (index 0 || index size) {return;}size--;if (index 0) {dummy dummy.next;return;}ListNode preNode dummy;for (int i 0; i index; i) {preNode preNode.next;}preNode.next preNode.next.next;}
}206. 反转链表
第一遍-双指针法
思路【这次偷懒了】 本来第一反应是利用栈先压栈后出栈但这样的操作过于麻烦还需要定义ListNode的类和在链表中添加ListNode的方法因此直接去看了代码随想录的思路果然比我的要简单很多
class Solution {public ListNode reverseList(ListNode head) {ListNode preNode null;ListNode currNode head;ListNode tmpNode null;while (currNode ! null) {tmpNode currNode.next;currNode.next preNode;preNode currNode;currNode tmpNode;}return preNode;}
}第二遍-递归法
因为第一遍从开始写到AC用时很短因此尝试了一下递归法也一遍AC了
class Solution {public ListNode reverse(ListNode preNode, ListNode currNode) {if (currNode null) return preNode;ListNode tmpNode currNode.next;currNode.next preNode;return reverse(currNode, tmpNode);}public ListNode reverseList(ListNode head) {return reverse(null, head);}
}
