# #1 Remove Duplicates From Linked List

###### tags:`linked list` `easy`

## Problem
You're given the head of a Singly Linked List whose nodes are in sorted order with respect to their values. Write a function that returns a modified version of the Linked List that doesn't contain any nodes with duplicate values. The Linked List should be modified in place (i.e,, you shouldn't create a brand new list), and the modified Linked List should still have its nodes sorted with respect to their values.

Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it's the tail of the list.

### Sample Input

1->1->3->4->4->4->5->6->6

### Sample Output

1->3->4->5->6

<br>

:::spoiler **Optimal Space & Time Complexity**

:::

<br>

:::spoiler Hint 1
The brute-force approach to this problem is to use a hash table or a set to keep track of all node values that exist while traversing the linked list and to simply remove nodes that have a value that already exists. This approach works, but can you solve this problem without using an auxiliary data structure?
:::

<br>

:::spoiler Hint 2
What does the fact that the nodes are sorted tell you about the location of all duplicate nodes? How can you use this fact to solve this problem with constant space?
:::

<br>

:::spoiler Hint 3
Since the linked list's nodes are sorted, you can loop through them and, at each iteration, simply remove all successive nodes that have the same value as the current node. For each node, change its next pointer to the next node in the linked list that has a different value. This will remove all duplicate-value nodes.
:::

<br>

<hr/>

## Solutions

### Official

// O(n) time | O(1) space - where n is the number of nodes in the Linked List
function removeDuplicatesFromLinkedList(linkedList) {
    let currentNode = linkedList;
    while (currentNode !== null) {
        let nextDistinctNode = currentNode.next;
        while (nextDistinctNode !== null && nextDistinctNode.value === currentNode.value
        { nextDistinctNode = nextDistinctNode.next; }
        currentNode.next = nextDistinctnode;
        currentNode = nextDistinctNode;
    }
    return linkedList;
}

// 以當下 node 不為 null 時，來 run 
// 將當下 node 的 next 設為另個 variable
// 條件：當 next 不為 null 且當前與 next 值相等時 -> 是把 nextNode 指到 nextNode 的 next，而非 currentNode 的

<br>

---

### Everyone's

:::spoiler 東

// Time O(n), Space O(1), n is the number of node in input linkedList
function removeDuplicatesFromLinkedList(linkedList) {
  let currNode = linkedList;
  while(currNode !== null){
    if(currNode.next !== null && currNode.value === currNode.next.value){
      let nonDupNode = currNode.next;
      while(nonDupNode !== null && currNode.value === nonDupNode.value){
          nonDupNode = nonDupNode.next;
      }
      currNode.next = nonDupNode;
    }
    currNode = currNode.next
  }
  return linkedList;
}
// line 5 的 if 其實跟 line 7 while 在做一樣的事情

:::

<br>

:::spoiler Raiy

/*
    time: O(n) - where n is the number of nodes in the Linked List
    space: O(1)
*/

function removeDuplicatesFromLinkedList(linkedList) {
  if(!linkedList) return null
  if(linkedList.next === null) return linkedList // 可拿掉
  
  let currentNode = linkedList
  let nextNode = currentNode.next

  while(nextNode !== null){
    if(currentNode.value === nextNode.value){
      currentNode.next = nextNode.next
      nextNode = nextNode.next // 可提到 outer
    }else{
      currentNode = nextNode
      nextNode = nextNode.next // 可提到 outer
    }
  }
  return linkedList;
}

:::

<br>

:::spoiler YC

/*
    time: O(n) - where n is the number of nodes in the Linked List
    space: O(1)
*/

function removeDuplicatesFromLinkedList(linkedList) {
  let root = linkedList;
  
  if (root === null) return null;

  while(root.next){
    if (root.value === root.next.value) root.next = root.next.next;
    else root = root.next;
  }
  
  return linkedList;
}

:::

<br>

:::spoiler Becky

//time: O(n) | space: O(1)
function removeDuplicatesFromLinkedList(linkedList) {
   let currentNode = linkedList;
    while (currentNode !== null && currentNode.next !== null) { 
        if (currentNode.value === currentNode.next.value){  
            currentNode.next = currentNode.next.next;         
        } else {  
            currentNode = currentNode.next;
        }
    }
    return linkedList;
}

:::

---

## Supplement / Discussion
1. check the flow

2. step by step

3. 如果題目給定並非 sorted 過的，那麼要如何處理？