算法-技巧篇-链表

学习核心

• 链表操作技巧（虚拟节点的引入）

学习资料

• 代码随想录-链表（203.移除链表元素）

移除链表元素

​ 虚拟节点的引入：移除链表元素，实际就是断开当前元素与上下节点的连接。参考下图所示分析，对于中间节点的操作，移除元素实际就是将当前元素的上一节点的next 指向当前节点的next。但对于头节点而言，其并没有上一个节点，因此此处会增设一个虚拟头节点，让操作方法更具通用性，而不需要额外对头节点进行处理

方案1：基于原链表进行操作

​ 如果是基于原链表操作，此处需单独处理头节点的情况，其他节点则可直接通过遍历实现（因为此处并不是双向链表，它无法直到当前节点的上一个节点prev，所以移除比较的并不是当前节点，而是当前节点的下一个节点信息）

• 单独处理头节点信息：此处需要用while子句判断头节点（因为可能每次移除头节点后会产生新的"头节点",因此要将头节点的情况全部排除）
• 遍历链表节点：如果当前节点指向的下一个节点满足删除条件，则将当前节点的next指向cur.next.next

public ListNode removeListNode1(ListNode head, int val) {

    // 头节点判断（此处用while是考虑到可能每次移除的都是头节点）
    while(head!=null && head.val==val) {
        head = head.next; // 移除头节点
    }

    // 定义链表指针
    ListNode cur = head;

    // 判断当前节点的下一个节点是否为待删除元素
    while (cur != null && cur.next != null) {
        // 判断当前节点是否为要删除的节点
        if (cur.next.val == val) {
            // 执行删除操作
            cur.next = cur.next.next;
        }
        // 节点后移
        cur = cur.next;
    }

    // 返回链表
    return head;
}

方案1：增设虚拟头节点进行操作

​ 通过增设虚拟头结点，让遍历方法更具通用性，不需要单独考虑头节点的情况。增设虚拟头结点这点在后续链表的操作场景中很有参考意义

public ListNode removeListNode2(ListNode head, int val) {

    // 增设虚拟头节点
    ListNode dummy = new ListNode(0,head);

    // 定义链表指针
    ListNode cur = dummy;

    // 从虚拟头结点开始遍历，判断当前节点的下一个节点元素是否为待删除元素，如果是则将当前节点的next指向下下个节点
    while (cur.next != null) {
        // 判断当前节点是否为要删除的节点
        if (cur.next.val == val) {
            // 执行删除操作
            cur.next = cur.next.next;
        }else{
            // 指针后移
            cur = cur.next;
        }
    }

    // 返回链表
    return dummy.next;
}