训练营day03:链表1-203.移除链表元素，707.设计链表，206.反转链表

203.移除链表元素

题目链接
https://leetcode.cn/problems/remove-linked-list-elements/description/
单链表里比较简单的题目了，我的第一版答案

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        ListNode curNode = head;
        ListNode preNode = null;
        while (curNode != null) {
            if (curNode.val == val) {
                if (head == curNode) {
                    head = curNode.next;
                } else {
                    preNode.next = curNode.next;
                }
            } else {
                preNode = curNode;
            }
            curNode = curNode.next;
        }
        return head;
    }
}

卡哥的解法

/**
 * 不添加虚拟节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}
注：卡哥还有一种增加虚拟节点的解法，这种解法代码更简洁，但平常我肯定不会使用这种解法，先忽略

题后感
1.和卡哥逻辑一致，主要区别就是头节点的单独处理，卡哥给的两种解法都是单独处理头节点，我的直接在循环里处理了
2.有个缓存节点pre，和卡哥不加虚拟节点的第一种解法一致，但卡哥答案理解起来逻辑更清晰
3.不加虚拟节点的第二种解法更简洁，更优秀

707.设计链表

题目链接
https://leetcode.cn/problems/design-linked-list/description/
这道设计题逻辑上、解法上没有难度，就是要细心细心再细心

206.反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }
}

题后感：
1.这题比较简单，双指针法还是比较常见的，但是我一开始就把两个临时变量赋值错了，漏了头节点（错误的给pre赋值head,cur赋值head.next,这样新head就要单独赋值了）
2.还有另外一种写法——递归法，两种写法逻辑是一样的，代码层面描述不同，感受一下

class Solution {
    public ListNode reverseList(ListNode head) {

        return reverse(null, head);
    }
    public ListNode reverse(ListNode pre,ListNode cur) {
        if (cur == null) return pre;
        ListNode tmp = cur.next;
        cur.next = pre;
        
        pre = cur;
        cur = tmp;

        return reverse(pre, cur);
    }
}