代码随想录第十二期集训营-第三天
今天是营中第三天训练日，内容包括链表的基础知识，力扣203、707以及206.
203.移除链表元素
删除链表元素时，要删除head和非head节点是两种操作。删除head时，直接让head = head.next、删除非head时，要让被删节点cur的前一个节点pre指向cur.next，也就是pre.next.next = cur.next。为了能统一操作，我们就采用虚拟头结点这种方式，创建一个虚拟头结点，让他指向原来的head，然后对原链表操作，这样就能统一删除操作，返回时返回虚拟头结点的下一个节点。
/**
* 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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
ListNode dummyNode = new ListNode(-1,head);
ListNode cur = dummyNode;
while(cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dummyNode.next;
}
}
另一种用双指针的思想，一个指针cur负责遍历链表找到删除元素，另一个指针pre负责删除。
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
ListNode dummyNode = new ListNode(-1,head);
ListNode cur = head;
ListNode pre = dummyNode;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return dummyNode.next;
}
}
707.设计链表
这题就是设计链表中的方法，都用虚拟头结点做就行。
206.反转链表
经典题，我看一些面试手撕都有这个。
第一种方法我用双指针，第二种是递归，正向递归，思想和双指针一样，都是一个指针，一个cur指向当前节点，一个pre为cur前一个节点。注意的是反转之前要有一个临时节点变量，负责记录cur.next，要不然反转之后找不到下一个节点了。
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode cur = head;
ListNode pre = null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
正向递归有意思的就是递归方法的返回值中的传参，要找对pre和cur。正向递归其实就是用递归方法代替了双指针中的while循环。
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
public ListNode reverse(ListNode pre,ListNode cur){
//判断cur是否为空，为空要么是原来就是空，要么就是遍历到结尾了
if(cur == null){
return pre;
}
//临时节点记录当前节点的下一个节点
ListNode temp = cur.next;
//反转
cur.next = pre;
//返回时，还是要找到前一个节点和当前节点，前一个节点就是此时的cur，当前节点就是此时的temp
return reverse(cur,temp);
}
}
还有一种方法为反向递归，需要通过递归找到最后一个节点，然后反转，最后返回最后一个节点。
class Solution {
public ListNode reverseList(ListNode head) {
//从后向前递归，找到最后一个节点，从后向前反转
//边界条件
if(head == null){
return null;
}
//找到最后一个节点
if(head.next == null){
return head;
}
//去找最后一个节点
ListNode last = reverseList(head.next);
//此时的head是last的前一个节点，开始反转
head.next.next = head;
head.next = null;
return last;
}
}
第三天打卡结束，其实是补卡
