A. Offer B. Offer C. Offer D. Offer

Topic describes

Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted.

Example 1:

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

Example 2:

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

Tip:

- The linked list contains at least two nodes. - All nodes in the list have unique values. - The given node is not a trailing node and must be a valid node in the list. - Do not return any results from your function.Copy the code

The code shown

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
  node.val = node.next.val;
  node.next = node.next.next;
};
Copy the code

Topic describes

Given the header pointer of a unidirectional linked list and the value of a node to delete, define a function to delete the 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] Explanation: Given the third node in your list with value 1, after calling your function, the list will be changed to 4 -> 5 -> 9.Copy the code

The code shown

Method 1: single pointer

/** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var deleteNode = function(head, val) { let p = head; if (head.val === val) return head.next; while(p) { if (p.next && p.next.val === val && ! p.next.next) { p.next = null; break; } if (p.val === val) { p.val = p.next.val; p.next = p.next.next; } p = p.next; } return head; };Copy the code

Method 2: Double pointer

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
  if (head.val === val) return head.next;
  let cur = head;
  let prev = head.next;
  while(prev) {
    if (prev && prev.val === val) {
      cur.next = prev.next;
    }
    cur = cur.next;
    prev = prev.next;
  }
  return head;
};
Copy the code

Complexity analysis:

Time complexity: O(n).

Space complexity: O(1).

conclusion

Double pointer performance is better than single pointer, the code is more concise.