Delete the NTH node from the list

Title description:

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Tip:

  • The number of nodes in the linked list is zerosz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Idea 1:

If the length of the list is len, the len-n node from the positive order is the deleted node. Find the node before the deleted node and point its next to the node after the deleted node.

Critical problem: when the deleted node is the first node

Virtual nodes are required to solve the above critical problems.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { if(head == null) return head; var p = head,len=1; while(p.next ! = null) { p = p.next; len++; } n = len-n; var node = new ListNode(-1); node.next = head; var q = node; while(n--) q = q.next; q.next = q.next.next; return node.next; };Copy the code

Idea 2: fast and slow pointer

Two Pointers p and q, first let q take n steps, after n steps, let P and Q go back one step at a time, until Q terminates at the end of the list. In this case, the position of the p pointer is the previous node of the node to be deleted. (The length of the linked list, q pointer takes n steps first, and the remaining steps are length-n. The first length-n node is the previous node of the node to be deleted. Therefore, after Q pointer takes n steps first, P pointer starts to take the remaining steps and reaches the previous node of the node to be deleted.)

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { if(head == null) return head; var node = new ListNode(-1); node.next = head; var p = node,q=node.next; for(var i = 0; i<n; i++){ q = q.next; } while(q! =null) { p = p.next; q = q.next; } p.next = p.next.next; return node.next; };Copy the code

readme

Algorithm small white one, record their own algorithm learning road. If you find any problems, please leave a message.