【LeetCode刷题】删除排序链表中的重复元素


题目链接:删除排序链表中的重复元素

题目

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例1:
输入:head = [1,1,2]
输出:[1,2]

示例2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]

解题

题目不难,有序的链表,直接快慢指针就可以解决问题了。

/**
 * 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) {
        if(head == null) return head;
        ListNode slow = head, fast = head.next;
        while(fast != null) {
            if(slow.val == fast.val) {
                slow.next = fast.next;
                fast = fast.next;
            } else {
                slow = slow.next;
                fast = fast.next;
            }
        }
        
        return head;
    }
}

时间复杂度:$$O(n)$$

改进

因为是线上判题,只看结果,所以直接修改了指针,没有释放被删除节点的空间,实际应用中,为了防止内存泄漏,C/C++应当及时释放掉内存,Java中应该及时将被删除节点从链表中分离出去,等待被JVM回收。

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【LeetCode刷题】删除排序链表中的重复元素


Just For Fun...