This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

59. Delete duplicate elements from the sorted list (remove-duplicates-from-sorted-list)

The label

  • The list
  • simple

The title

Leetcode portal

Let’s just open leetCode.

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once.

Returns a linked list of results, also in ascending order.

Basic steps

The basic operation of a linked list. Note that the linked list is already an ascending list, with repeated elements adjacent.

  1. We set the pointercurPoints to the head node of the linked list
  2. Iterate over the linked list. If the currentCur and cur. NextThe correspondingElements of the same“, we remove cur.next from the list and point directly to the next node.cur.next = cur.next.next
  3. Otherwise, there are no other and in the linked listcurThe corresponding element is the same node, so the current pointer is moved backcurPoint to thecur.next.
  4. To traverse thecur.next === nullI’m done. I go back to head;

Writing implement

var deleteDuplicates = function(head) {
  // head === null
  if(! head) {return head;
  }
  let cur = head;
  while (cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else{ cur = cur.next; }}return head;
};
Copy the code

60. Delete duplicate elements II from sorted lists (remove-duplicates-from-sorted-list-ii)

The label

  • The list
  • medium

The title

Leetcode portal

Let’s just open leetCode.

There is a linked list in ascending order, and you are given the head node of the linked list. Please delete all the nodes in the linked list that have duplicate numbers, and only keep the original list that does not have duplicate numbers.

Returns a linked list of results, also in ascending order.

The basic idea

An updated version of the previous problem. Note that you are removing all nodes that contain duplicate cases. So we need a while to loop through the node after the repeated element.

Basic steps

  1. Create a virtual head node (to keep the rule simple and not special to head nodes). If you do not add the preHead, the head node of the linked list may be deleted.
  2. Let’s make the current pointercurPoints to the precursor node of the linked list, and then starts traversing the list.
  3. Judge the repetition in the same wayJudge between cur.next. Val and cur.next-next-val.
    • Not equal, not repeated,curStraight back.
    • Equal, there is duplication, first record the repeated val, the loop continues to iterate and compare the repeated values, delete all repeated elements.
  4. Return the post-prehead, which is the header.

Writing implement

var deleteDuplicates = function(head) {
  if(! head) {return head;
  }
  // Create a virtual head node to keep the rule simple without special handling of head nodes
  let preHead = new ListNode(0);
  preHead.next = head;
  // Set the current pointer to preHead
  let cur = preHead
  while (cur.next && cur.next.next) {
    // Do not repeat the case, the current pointer (cur) moved back
    if(cur.next.val ! == cur.next.next.val) { cur = cur.next; }else {
      // If there is a duplicate node, iterate to remove the duplicate node, first record the duplicate value
      let duplicateNum = cur.next.val;
      while(cur.next && cur.next.val === duplicateNum) { cur.next = cur.next.next; }}}return preHead.next;
};
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference