刷刷刷Day3| 203.移除链表元素 ，707.设计链表 ，206.反转链表

203.移除链表元素

LeetCode题目要求

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例1
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

解题思路

根据链表的结构，移除链表的一个元素后，实际需要将被删除元素后的元素指向被删除元素的前一个元素
通过一个简单链表结构，并借助虚拟节点，来完成移除元素的操作

/**
 * 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) {
        // 移除链表的元素，存在3中情况
        //1. 如果被删除的元素是 ‘head’ 节点，那么新的头节点就是 head.next
        //2. 如果被删除的元素是 tail 节点，那么就直接删除了
        //3. 如果呗删除的元素是 中间 节点，那么要指针重新指向，前个节点的 next 为 中间节点的后一个节点

        // 借助一个虚拟头节点，屏蔽掉差异点
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode curr = pre;
        // 根据 val 删除元素，需要遍历 ListNode
        while (curr != null) {
            if (curr.val == val) {
                //如果找到了目标值，那么把 前个元素的next 指向 当前额下一个元素
                pre.next = curr.next;
            } else {
                //如果未找到，则当前值变成下一个的pre
                pre = curr;
            }
            
            curr = curr.next;
        }
        return dummy.next;
    }
}

重难点

• 借助虚拟节点进行操作，避免删除的是头节点做不必要的处理
• 删除后元素的指针指向
  如 A -> B -> C, 如果删除的是B，那么指针指向变换，A不再指向B，而是指向C，即 A -> C, 这里是需要注意
  附：学习资料链接

707.设计链表

LeetCode题目要求

解题思路

重难点

附：学习资料链接

206.反转链表

LeetCode题目要求

解题思路

重难点

附：学习资料链接