Topic describes

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.

Analysis of the

Input: head node of the list Output: head node of the list after transformation

Their thinking

We can solve this problem in two ways, the first way is the two-pointer method that I thought of at the beginning, and the other way is a traversal provided on the website

Double pointer

For the two-pointer solution, we need to define two Pointers, fast and slow, where fast goes first. In this case, I’m going to keep fast going until its val does not equal the value of slow.

Here’s a picture:

The first operation occurs when Fast goes from dummyHead to 1, and the second operation is from 3, so FOR convenience, I’ll take the second example.

Slow points to 1, fast points to 3, and obviously what we need to do is slow. Next points to 3, so that all intermediate elements that repeat are skipped, leaving only 1, ➡️, and 3 in the list.

Let’s look at the code:

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var deleteDuplicates = function (head) {
  if(! head)return null;

  const dummyHead = new ListNode(null, head);
  let slow = dummyHead,
    fast = dummyHead;

  while (fast) {
      // When fast and slow point to different things, we operate to point slow next to fast
      // Only one of the duplicate elements is kept, and the rest are deleted
    if(slow.val ! == fast.val) { slow.next = fast; slow = fast; }/ / move fast
    fast = fast.next;
  }
  // When fast is null, there is no link to 🔗
  slow.next = fast;

  return dummyHead.next;
};
Copy the code

A traversal

This method is the official solution of the problem, which is easier than mine.

If you find a contiguous element, delete all the next nodes that are repeated behind it and iterate backwards. Let’s look at the code:

code

var deleteDuplicates = function (head) {
  if(! head)return null;
  let cur = head

// Delete next
  while (cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else{ cur = cur.next; }}return head;
};
Copy the code