package LeetCode; public class LeetCode203 { // https://leetcode.com/problems/remove-linked-list-elements/description/ // 不使用虚拟头结点 // 时间复杂度: O(n) // 空间复杂度: O(1) public ListNode removeElements(ListNode head, int val) { // 需要对头结点进行特殊处理 while(head != null && head.val == val){ ListNode node = head; head = head.next; } if(head == null) return head; ListNode cur = head; while(cur.next != null){ if(cur.next.val == val){ ListNode delNode = cur.next; cur.next = delNode.next; } else cur = cur.next; } return head; } // 弄了一个虚拟节点(不用对头结点再做处理了) public ListNode removeElements2(ListNode head, int val) { // 创建虚拟头结点 ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode cur = dummyHead; while(cur.next != null){ if(cur.next.val == val ){ ListNode delNode = cur.next; cur.next = delNode.next; } else cur = cur.next; } return dummyHead.next; } // 递归的方式来做 public ListNode removeElements3(ListNode head, int val) { if(head == null) return head; // 用下一个节点跟value比较 ListNode res = removeElements3(head.next, val); if(head.val == val) return res; else{ head.next = res; return head; } } // 递归的方式来做--->其实就是一个子串删除的问题。 public ListNode removeElements4(ListNode head, int val) { if(head == null) return head; // 删除重复的节点，拿到子串 head.next = removeElements4(head.next, val); // 如果头节点是要删除的节点，返回子串。如果不是，返回当前子串 return head.val == val ? head.next : head; } public static void main(String[] args) { int[] nums = {1, 2, 6, 3, 4, 5, 6}; ListNode head = new ListNode(nums); System.out.println(head); ListNode res = (new LeetCode203()).removeElements3(head, 6); System.out.println(res); } }