linye's Blog

全端工程師心得分享

0%

[LeetCode]83. Remove Duplicates from Sorted List

發表於 分類於 ，

Algorithm I 筆記撰寫計畫 第八天第二題，共兩題。

給你一個 Linked List 的 head ，刪除所有重複的節點，然後回傳新的 Linked List

點我開啟限制與範例

限制:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

Example 1:

example-image-1

1
2
Input: head = [1,1,2]
Output: [1,2]

Example 2:

example-image-2

1
2
Input: head = [1,1,2,3,3]
Output: [1,2,3]

Definition for singly-linked list.

1
2
3
4
5
6
7
8
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

筆記

這題簡單的讓我們練習了一下 Linked List

步驟如下

  1. 遍歷 List
  2. 每個 Node 都跟 Node.next 做比較
    • 如果相等: 把 Node.next 指向 Node.next.next 重複直到不相等
  3. 回傳 Head

TS iterative solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function deleteDuplicates(head: ListNode | null): ListNode | null {
  let node = head;// 當前節點

  // 遍歷 list
  while (node?.next) {
    // 重複把 node.next 指向 node.next.next 直到 val 不相等
    while (node.next && node.val === node.next.val) {
      node.next = node.next.next;
    }
    node = node.next;
  }
  return head;
};

Java recursive solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

  public ListNode deleteDuplicates(ListNode head) {
    traverse(head);
    return head;
  }

  public void traverse(ListNode node) {
    if (node == null || node.next == null) return;
    if (node.val == node.next.val) {
      node.next = node.next.next;
      traverse(node);
    } else {
      node = node.next;
      traverse(node);
    }
  }
}

成績

Language Runtime Beats Memory Usage Beats
Java 1 ms 80.63% 43.9 MB 73.27%
TypeScript 77 ms 95.35% 45.4 MB 22.74%

score-image