代码随想录算法训练营第3天| 203.移除链表元素 ，707.设计链表 ，206.反转链表

学习任务：

• 链表理论基础
• Leetcode203.移除链表元素
• Leetcode707.设计链表
• Leetcode206.反转链表

Leetcode203.移除链表元素

难度：简单 | 相关标签：递归、链表

• 题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

• 思路： 移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。所以头结点要单独考虑，为了简化操作，我们可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

• 注意：

  1. 如何设置虚拟头结点：ListNode dummy = new ListNode(); dummy.next =head;
  2. return 头结点的时候，别忘了 return dummy.next;， 这才是新的头结点
  3. 在遍历链表时，我们通常要设置一个cur指针用于遍历，而不是操作头指针，因为最后我们要返回头指针

• 代码：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
    	// 添加一个虚拟头结点为新的头结点
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur= dummy;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

• 反思： 可以通过画图理解算法逻辑，注意熟练使用虚拟头结点来操作链表

Leetcode707.设计链表

难度：中等 | 相关标签：设计、链表

• 题目： 你可以选择使用单链表或者双链表，设计并实现自己的链表。

  1. 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
  2. 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
     实现 MyLinkedList 类：
     1. MyLinkedList() 初始化 MyLinkedList 对象。
     2. int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
     3. void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
     4. void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
     5. void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
     6. void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

• 注意：

  1. 在进行第n个结点的删除和插入操作时，要找的是第n-1个结点，cur指向n-1, cur.next指向n
  2. 进行插入操作时，一定要注意操作的先后顺序，搞不清的时候画图

• 代码： 单链表

class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {
    //存储链表元素的个数
    int size;
    //头结点
    ListNode head;

    // 初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    // 获取下标为 index 的结点的值
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur= head;
        for (int i = 0; i <= index; i++) {
            cur= cur.next;
        }
        return cur.val;
    }
    
    // 插入头结点
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    // 插入尾结点
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }
    
    //删除链表中下标为 index 的节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

• 反思： 很容易出错，要细心，好好理解链表的特点

Leetcode206.反转链表

难度：简单 | 相关标签：递归、链表

• 题目： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

• 思路： 改变链表的next指针的指向，将链表反转。首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。然后开始反转操作，首先要把 cur->next 节点用temp指针保存一下,因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
  最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

• 注意：

  1. 用的的指针比较多，一定要搞清楚其中的关系和先后顺序

• 代码：

双指针法：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = new ListNode();
        ListNode cur = new ListNode();
        prev = null;
        cur = head;
        while(cur != null){
            ListNode temp = new ListNode();
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

递归法：

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

• 反思： 递归法还是掌握不好，看了视频讲解，再好好领悟我，自己写不出来