代码随想录算法训练营第三天 | 203-移除链表元素、707-设计链表、206-反转链表
LeetCode203 移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/
文章讲解：https://programmercarl.com/0203.移除链表元素.html
视频讲解：https://www.bilibili.com/video/BV18B4y1s7R9/?vd_source=b989f2b109eb3b17e8178154a7de7a51
引入虚拟头节点，这样可以使用一套规则去删除链表中节点，处理起来更加方便
如果是C++还得额外考虑内存回收，但我用的是Java，虚拟机自动回收内存hh
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummyHead = new ListNode(0,head);ListNode p = dummyHead;while(p.next != null){if(p.next.val == val){p.next = p.next.next;}else{p = p.next;}}return dummyHead.next;}
}
LeetCode707 设计链表
题目链接：https://leetcode.cn/problems/design-linked-list/description/
文章讲解：https://programmercarl.com/0707.设计链表.html
视频讲解：https://www.bilibili.com/video/BV1FU4y1X7WD/?vd_source=b989f2b109eb3b17e8178154a7de7a51
做这种涉及到指针的题目，要时刻明确当前状态下指针到了什么位置，注意细节和合法范围条件，小心在一些细小的地方出错（比如>和>=）
class MyLinkedList {class Node{int val;Node next;public Node(){}public Node(int val, Node next){this.val = val;this.next = next;}}Node dummyHead;int size;public MyLinkedList() {size = 0;dummyHead = new Node(0, null);}public int get(int index) {if(index < 0 || index >= size){return -1;}Node cur = dummyHead;for(int i = 0;i <= index;i++){cur = cur.next;}return cur.val;}public void addAtHead(int val) {Node newNode = new Node(val, dummyHead.next);dummyHead.next = newNode;size++;}public void addAtTail(int val) {Node cur = dummyHead;while(cur.next != null){cur = cur.next;}Node newNode = new Node(val, null);cur.next = newNode;size++;}public void addAtIndex(int index, int val) {if(index < 0 || index > size){return;}Node cur = dummyHead;Node pre = null;for(int i = 0;i <= index;i++){pre = cur;cur = cur.next;}Node newNode = new Node(val, cur);pre.next = newNode;size++;}public void deleteAtIndex(int index) {if(index < 0 || index >= size){return;}Node cur = dummyHead;Node pre = null;for(int i = 0;i <= index;i++){pre = cur;cur = cur.next;}pre.next = cur.next;size--;}
}
LeetCode206 反转链表
题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
文章讲解：https://programmercarl.com/0206.翻转链表.html
视频讲解：https://www.bilibili.com/video/BV1nB4y1i7eL/?vd_source=b989f2b109eb3b17e8178154a7de7a51
采用双指针的思路，cur指向当前节点，pre指向上一个节点，temp指向下一个节点，仔细画画图分析遍历过程，还是很清晰的
class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;while(cur != null){ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}
依照双指针解法的思路，还可以使用递归解决此问题：
class Solution {public ListNode reverse(ListNode cur, ListNode pre){if(cur == null){return pre;}ListNode temp = cur.next;cur.next = pre;return reverse(temp, cur);}public ListNode reverseList(ListNode head) {return reverse(head, null);}
}