江苏网站建设平台/如何做百度竞价推广

题目

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

目录

题目

题目分析

代码深刻理解

题目分析

   直接使用原来的链表来进行移除。

   移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

代码深刻理解

/*** 添加虚节点方式* 时间复杂度 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 != valListNode 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;
}

跟着代码随想录学习算法,大家一起进步