一、题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
实例1:
输入： head = [1,2,6,3,4,5,6], val = 6 输出： [1,2,3,4,5] 解释: n = 3 代表是由数字1到9组成了一个 int[3][3] 的数组
网络异常，图片无法展示
|
实例2:
输入： head = [], val = 1 输出： []
实例3：
输入： head = [7,7,7,7], val = 7 输出： []
二、思路分析
直接使用原链表进行操作， 如果元素相同则next==下一个元素， 如果不同则继续
卡尔把这种方法称为： 不添加虚拟节点and pre Node方式， 同时还有另外两种方法， 分别为： 不添加虚拟节点方式和添加虚拟节点
三、java代码
/** * 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) { 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; } }
四、总结
实际上也就只想到了这一种方式， 并用这种方式完成了代码， 卡尔的代码随想录里还讲解了其他两种方式， 如下所示
/** * 添加虚节点方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */ public ListNode removeElements(ListNode head, int val) { if (head == null) { return head; } // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作 ListNode dummy = new ListNode(-1, head); ListNode pre = dummy; ListNode cur = head; while (cur != null) { if (cur.val == val) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return dummy.next; } /** * 不添加虚拟节点方式 * 时间复杂度 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; }
