This is the 23rd day of my participation in the August More Text Challenge

Deletes a node in a linked list

18. Remove nodes from the list

Given a head pointer to a one-way linked list and the value of a node to delete, define a function to delete that node.

Returns the head node of the deleted list.

Example 1:

Input: head = [4,5,1,9], val = 5 Output: [4,1,9]Copy the code

Example 2:

Input: head = [4,5,1,9], val = 1 Output: [4,5,9]Copy the code

Note: The problem ensures that the values of the nodes in the linked list are not the same

Answer key

Method 1 uses head. Next

Use the head. Next method to solve

 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
 / * * *@param {ListNode} head
  * @param {number} val
  * @return {ListNode}* /
 var deleteNode = function(head,val){
   if(head.val === val){
     return head.next;
   }
   head.next = deleteNode(head.next,val);
   return head;
 }
Copy the code

Method two sentinel node

 var deleteNode = function(head,val){
   let pre = new ListNode(-1); // The sentinel node
   pre.next = head;
   
   let node = pre;
   while(node.next){
     if(node.next.val === val){
       node.next = node.next.next;
       break;
     }
     node = node.next;
   }
   return pre.next;
 }
Copy the code

Time complexity O(n), space complexity O(1)

Reorder the array so that the odd number precedes the even number

21. Reorder the array so that the odd number precedes the even number

Difficulty: Easy

Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half.

Example:

Input: nums = [1,2,3,4] output: [1,3,2,4] note: [3,1,2,4] is also one of the correct answers.Copy the code

Tip:

  1. 0 <= nums.length <= 50000
  2. 1 <= nums[ i ] <= 10000

Answer key

Method one sort function

 / * * *@param {number[]} nums
  * @return {number[]}* /
 var exchange = function(nums) {
   return nums.sort((a,b) = >b%2-a%2)};Copy the code

Law 2 violence

Need to do 2 cycles:

  • The first loop finds even and odd numbers and puts them in their respective arrays.
  • The second loop concatenates the two arrays
 var exchange = function(nums){
   const arr = [];
   const brr = [];
   nums.forEach(item= > {
     item % 2 ? arr.push(item) : brr.push(item);
   });
   return arr.concat(brr);
 }
Copy the code

Both time complexity and space complexity are O(n).

Method three double pointer method

Pointer I to the head of the array, and pointer J to the tail of the array. The process is as follows:

  • I moves to the right until it hits an even number; J moves to the left until it hits an odd number
  • Check whether I is less than j. If so, exchange the elements of I and J and go back to the previous step to continue moving. Otherwise end the loop
 var exchange = function(nums){
   const length = nums.length;
   if(! length){return [];
   }
   let i = 0,j = length - 1;
   while(i < j){
     while(i < length && nums[i] % 2= = =1) i++;
     while(j >= 0 && nums[j] % 2= = =0) j--;
     if(i < j){ [nums[i],nums[j]] = [nums[j],nums[i]]; i++; j--; }}return nums;
 }
Copy the code

Time complexity O(n), space complexity O(1)

Practice every day! The front end is a new one. I hope I can get a thumbs up