今天是营中第三天训练日，内容包括链表的基础知识，力扣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;
    }   
}

第三天打卡结束，其实是补卡