Day4 | Leetcode203、707

今天是链表相关题目一、链表的定义classListNode{intval;// ① 成员变量存储节点的值整数ListNodenext;// ② 成员变量指向下一个节点的引用形成链// ③ 无参构造方法创建一个空节点val 默认 0next 默认 nullListNode(){}// ④ 带一个参数的构造方法创建节点并赋值 valnext 默认为 nullListNode(intval){this.valval;}// ⑤ 带两个参数的构造方法创建节点并赋值 val 和 nextListNode(intval,ListNodenext){this.valval;this.nextnext;}}各部分的含义和作用部分作用int val存储当前节点存放的数据这里是一个整数。在链表题目中val就是节点里的值比如1 → 2 → 3中的 1、2、3。ListNode next这是一个引用类型变量指向链表中的下一个节点。如果当前节点是最后一个next null。通过这个引用多个ListNode对象就能串联成链表。无参构造ListNode()创建一个节点不设置初始值val默认为 0next默认为 null。可以用在需要先创建节点后再赋值的场景不过链表题目中较少直接使用。单参构造ListNode(int val)最常用的构造方法创建节点并直接存入值新节点的next自动为 null。例如new ListNode(5)创建一个值为 5 的尾节点。双参构造ListNode(int val, ListNode next)创建节点并同时指定值和下一个节点。例如new ListNode(3, nextNode)创建一个值为 3 且指向nextNode的节点常用于快速构建链表。在链表题目中的应用当你需要在 LeetCode 或面试中操作链表时你会用到这个类来创建节点ListNode node new ListNode(10);连接节点node.next anotherNode;遍历链表while (head ! null) { ... head head.next; }例如要构造链表1 - 2 - 3可以写ListNodenode3newListNode(3);ListNodenode2newListNode(2,node3);ListNodenode1newListNode(1,node2);// 或者更简洁地链式创建ListNodeheadnewListNode(1,newListNode(2,newListNode(3)));链表就相当于一个实体类 包含元素 和构造方法203移除链表元素1.判断头节点 然后处理后续节点/** * 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; } * } */classSolution{publicListNoderemoveElements(ListNodehead,intval){//先判断头节点是否为目标值while(head!nullhead.valval){headhead.next;}if(headnull){returnhead;}ListNodecurrhead;while(curr!nullcurr.next!null){if(curr.next.valval){curr.nextcurr.next.next;}else{currcurr.next;}}returnhead;}}解法二创建一个虚拟节点指向头节点/** * 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; } * } */classSolution{publicListNoderemoveElements(ListNodehead,intval){//创建一个节点指向链表ListNodedummynewListNode();dummy.nexthead;ListNodecurdummy;while(cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}}returndummy.next;}}二 设计一个链表注意点 index是需要插入和删除的节点 循环的时候 要用index-1找出前面的节点classMyLinkedList{privatestaticclasslistNode{intval;listNode next;listNode(intval){this.valval;}}privateintsize;privatelistNode head;//初始化链表publicMyLinkedList(){this.size0;this.headnull;}publicintget(intindex){if(index0||indexsize){return-1;}//定义一个节点指向头结点listNode currenthead;for(inti0;iindex;i){currentcurrent.next;}returncurrent.val;}publicvoidaddAtHead(intval){//在头结点上插入一个节点listNode currentnewlistNode(val);current.nexthead;headcurrent;size;return;}publicvoidaddAtTail(intval){//在尾结点上插入一个节点if(size0){addAtHead(val);return;}listNode newNodenewlistNode(val);listNode curhead;while(cur.next!null){curcur.next;}cur.nextnewNode;size;return;}publicvoidaddAtIndex(intindex,intval){if(index0||indexsize){return;}if(index0){addAtHead(val);return;}if(indexsize){addAtTail(val);return;}//插入到中间 需要找到前一个节点和后一个节点listNode prehead;for(inti0;iindex-1;i){prepre.next;}listNode newNodenewlistNode(val);newNode.nextpre.next;pre.nextnewNode;size;return;}publicvoiddeleteAtIndex(intindex){if(index0||indexsize){return;}if(index0){headhead.next;}else{listNode prehead;for(inti0;iindex-1;i){prepre.next;}pre.nextpre.next.next;}size--;}}/** * 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); */