美文网首页
83. 删除排序链表中的重复元素

83. 删除排序链表中的重复元素

作者: 衣锦昼行 | 来源:发表于2019-07-30 15:09 被阅读0次

    给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
    示例 1:
    输入: 1->1->2
    输出: 1->2

    示例 2:
    输入: 1->1->2->3->3
    输出: 1->2->3

    题解: 首先我们可以看到题目中有说明是排序链表,所以重复的元素一定会出现在相邻的位置,如果它是重复的,我们则将结点的next指针指向重复元素的下一个结点。比如示例2,1和1重复,则将第一个1的next指针指向2即可。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode l = head;
            while (l != null && l.next != null){
                if(l.val == l.next.val){
                    l.next = l.next.next;
                }
                else
                    l = l.next;
            }
            return head;
        }
    }
    

    复杂度分析

    时间复杂度:O(n),因为列表中的每个结点都检查一次以确定它是否重复,所以总运行时间为 O(n),其中 n 是列表中的结点数。

    空间复杂度:O(1),没有使用额外的空间。

    相关文章

      网友评论

          本文标题:83. 删除排序链表中的重复元素

          本文链接:https://www.haomeiwen.com/subject/wqdnrctx.html