This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Removes a linked list element

Val == val; delete all nodes in the list where node. val == val and return the new head Node.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6Copy the code

Example 2:

Input: head = [], val = 1Copy the code

Example 3:

Input: head = [7,7,7], val = 7Copy the code

Tip:

  • The nodes in the list are in the range[0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= k <= 50

Thought analysis

A simple linked list problem like this is more about your programming ability than your algorithmic ability, and this article will give you four solutions: the general solution, the optimal solution using virtual headers, the recursive solution, and a universal way to change the linked list.

The code shown

Solution 1: common solution, time complexity is O(n){O(n)}O(n), space complexity is also O(1){O(1)}O(1).

    public ListNode removeElements(ListNode head, int val) {
        / / method
        // If the header is the target in the first place
        while(head ! =null && head.val == val){
            head = head.next;
        }
        if (head == null) {return null;
        }
        ListNode prev = head;
        while(prev.next ! =null) {if (prev.next.val == val){
                prev.next = prev.next.next;
            } else{ prev = prev.next; }}return head;
    }
Copy the code

Solution two: using virtual header optimization, the time complexity is O(n){O(n)}O(n), the space complexity is O(1){O(1)}O(1).

      public ListNode removeElements(ListNode head, int val) { 
				ListNode dumpHeader = new ListNode(val+1,head);
        ListNode prev = dumpHeader;
        while(prev.next ! =null) {if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else{ prev = prev.next; }}return dumpHeader.next;
      }
Copy the code

Solution three: recursive solution

		public ListNode removeElements(ListNode head, int val) { 	 
			 if (head == null) {return null;
        }
        head.next = removeElements(head.next,val);
        if (head.val == val){
            return head.next;
        } else {
            returnhead; }}Copy the code

conclusion

Simple topics should be able to master a variety of solutions as far as possible, but also to master the optimal solution, linked list writing is a test of programming ability, to be rigorous and careful.