LeetCode203.移除链表元素
● 今日学习的文章链接和视频链接
题目链接
● 自己看到题目的第一想法
之前做这道题时想的不是很清楚，浅看了一下代码随想录的思路，又重新写了一边。删除链表中的结点，实际上需要两个指针，找到待删除的结点后，结点前的一个指针指向该节点的后一个指针。如果不构造虚拟头节点，那么对于头节点的处理和后续节点的处理逻辑就比较有差异，因为头节点没有前一个结点 了，直接重置头指针就可以。所以，我们想保持操作的一致性，就可以用一个虚拟结点作为头节点的前一个结点。
具体代码如下：
//重新思考这个问题 public ListNode removeElements2(ListNode head, int val) { //要删除一个节点必须要保存节点的前一个值，让它的指针指向要删除节点的后一个节点 //但是如果是头结点的话就要考虑到它没有前置结点这个问题,所以要用循环去处理 //如果不是头结点，就可以借由前置结点去删除 while (head != null && head.val == val) { head = head.next; } ListNode cur=head;//走到这里说明cur的结点值一定不是要删除的值 //当前结点不为空，那么才可以取cur.next while (cur != null && cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next;//把右边的值赋值给左边,所以可以取到这个值 // 当删除结点的时候，指针自己就跳到下一个结点了，不需要再挪动指针 } else { cur = cur.next; } } return head; } //方法二：构造虚拟头节点 public ListNode removeElements3(ListNode head, int val) { //在第一种方法中，我们头结点的处理逻辑和后面结点的处理逻辑是分开的，这主要是因为头节点没有前置结点 //如果头节点也有前置结点，那么我们删除的逻辑就可以保持一致 ListNode tmpNode = new ListNode(-1); tmpNode.next = head; ListNode cur = tmpNode; while (cur != null && cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return tmpNode.next; }
● 看完代码随想录之后的想法
大致思路是一致的
● 自己实现过程中遇到哪些困难
在移动指针的时候没有想清楚这个过程，通过debug后发现要分情况移动指针，如果删除了元素，指针是自动更新的；如果没有删除元素，指针才需要往后移动
● 今日收获，记录一下自己的学习时长
1.2h
● 今日学习的文章链接
题目链接：
● 自己看到题目的第一想法
没想明白这个头指针怎么搞，看了一下代码随想录的思路，发现要弄一个虚拟结点，但是我一时还没想明白要是没有虚拟结点代码怎么写。那么就是说，插入或者删除操作的时候还要判断当前结点是不是头节点，如果是的话要单独处理，这样操作上就复杂了，所以还是利用一个虚拟头节点比较好。
class MyLinkedList { private ListNode head = new ListNode(); private int size = 0; public MyLinkedList() { } public int get(int index) { if (index >= size) { return -1; } ListNode cur = head; while (index-- >= 0) { cur = cur.next; } return cur.val; } public void addAtHead(int val) { ListNode node = new ListNode(val); node.next = head.next; head.next = node; size++; } public void addAtTail(int val) { ListNode tail = head; int tmp = size; while (tmp-- > 0) { tail = tail.next; } ListNode node = new ListNode(val); tail.next = node; tail = node; size++; } public void addAtIndex(int index, int val) { //要找到当前结点前一个结点的指针 if (index >= size) { return; } ListNode cur = head; while (index-- > 0) { cur = cur.next; } ListNode node = new ListNode(val); node.next = cur.next; cur.next = node; size++; } public void deleteAtIndex(int index) { if (index >= size) { return; } ListNode cur = head; while (index-- > 0) { cur = cur.next; } cur.next = cur.next.next; size--; } }
● 看完代码随想录之后的想法
在这里插入结点的循环条件容易想不清楚，只要代入0和1看一下循环过程会不会出现异常就行了
然后头尾的插入操作可以偷懒用addAtIndex就行
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 > size) { return; } ListNode cur = head; while (index> 0) { cur = cur.next; index--; } ListNode node = new ListNode(val); node.next = cur.next; cur.next = node; size++; }
● 自己实现过程中遇到哪些困难
前几次提交不通过，后来发现操作循环变量的时候直接把size--了，导致了出错，所以一定要想清楚哪些变量是一个全局重要的
● 今日收获，记录一下自己的学习时长
1.2h
● 今日学习的文章链接
题目链接：
● 自己看到题目的第一想法
反转链表到底是一个什么过程，其实就是遍历所有的结点，让当前结点指向前一个结点；因此在反转的过程中必要条件是当前结点存在且我们知道它的其前置结点，而且反转指针之前要提前保存下一个遍历的位置，否则我们就丢失后面的链表了
public ListNode reverseList(ListNode head) { //要翻转当前结点，既要让当前结点的指针反转指向其前一个结点，还要提前保存下一个结点的指针 // 所以当前结点必须存在且有下一个结点才需要反转指针? //非也，只要反转当前结点的指针就行，不管它有没有下一个结点，反转为指向前一个就行 ListNode cur = head; ListNode next; ListNode pre = null; while (cur != null ) { next = cur.next;//先保存下一个 cur.next = pre;//反转指针 pre = cur;//当前结点变成前置结点 cur = next;//指针往后遍历 } return pre; }
● 看完代码随想录之后的想法
这道题目还可以用递归的写法，为什么？因为循环里的操作是一样的，那么只要改变每次调用该循环的初始条件就行了，并且明确好终止条件，根据双指针的写法可以直接改为递归的写法
//方法二，递归写法 public ListNode reverseList3(ListNode head) { return reverse(head, null); } private ListNode reverse(ListNode cur, ListNode pre) { if (cur == null) { return pre; } ListNode next = cur.next; cur.next = pre; return reverse(next, cur); }
● 自己实现过程中遇到哪些困难
什么情形下可以用递归还没太明白
● 今日收获，记录一下自己的学习时长
1h