LeetCode #83 Remove Duplicates from Sorted List 已排序串列移除重複元素

Klook.com
文章觀看次數: 370

英文原文如下

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

中文翻譯

給予一個已排序的鏈結串列的頭節點(head)，刪除所有重複的元素來讓每個元素只出現一次。

回傳已排序的鏈結串列。

範例及題目限制

⬆️ 還用上了保證的字眼 – 絕對是升冪排序哈哈哈

解題思路

第三點限制 ➡ 這個列表是按升冪排序的。

我想到的第一個解決方案，是使用迭代來檢查下一個數字是否相同，如果相同就跳過它，如果不同就將它添加到一個新的鏈結串列中。

C# 解決方案

方案1 – 簡單的遞迴

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        
        ListNode resNode = new ListNode();
        
        if(head == null){return head;}
        ListNode copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                ListNode newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            
            head = head.next;
        }
            
        return resNode;
    }
}

時間複雜度 : O(n)

方案2 – LINQ

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode resNode = new ListNode();
        List<int>valList = new List<int>();

        //1.get val list distinct first
        if(head == null){return head;}
        while(head != null)
        {
            valList.Add(head.val);
            head = head.next;
        }
        valList = valList.Distinct().OrderBy(x => x).ToList();
        
        
        //2.remake a linked list and return
        resNode.val = valList[0];
        ListNode lastNode = resNode;
        
        for(int i =1;i<valList.Count;i++)
        {
            ListNode nowNode = new ListNode();
            nowNode.val = valList[i];
            lastNode.next = nowNode;
            lastNode = nowNode;
        }

        return resNode;
    }
}

時間複雜度 : O(n log n)

在我們的第二個解決方案中，我們將整個連結串列的值取出，並將它們保存在一個整數列表中。

接著，我們使用 LINQ的語法來排除重複殖，再重新構建一個新的鏈結串列。

Java解決方案

方案1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode resNode = new ListNode();
        
        if(head == null){return head;}
        ListNode copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                ListNode newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            head = head.next;
        }
        return resNode; 
    }
}

運行時間 : 1ms、0ms、1ms

Python3 解決方案

方案1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        resNode = ListNode()
        if(head == None):
            return head
        
        copyNode = resNode
        copyNode.val = head.val
        
        while(head!=None):
            if(copyNode.val!=head.val):
                newNode = ListNode()
                newNode.val = head.val
                
                copyNode.next = newNode
                copyNode = newNode
            head = head.next
        return resNode

JavaScript 解決方案

方案1

/**
 * 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) {
        var resNode = new ListNode();
        
        if(head == null){return head;}
        var copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                var newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            head = head.next;
        }
        return resNode; 
};

結論

這題看起來用一個簡單的迴圈就可以解決了

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我分享，那都是對我的小小支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Remove Duplicates from Sorted List – LeetCode

一些隨機文章

標籤

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *