一、leetcode算法
1、删除排序链表中的重复元素
1.1、题目
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。
示例 1:
输入:head = [1,1,2]
输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]
1.2、思路
思路一:由于链表是排序好的,那么我们只需要从第一个开始,让他们两个之间相互比较,假如第一个和第二个相等,那么就把第一个节点的next指向第三个节点的位置,这样重复的第二个就被删掉了,直到遍历完整个链表。
1.3、答案
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null){ return head; } //定义一个游标,用来判断链表是否遍历完 ListNode pre = head; //判断游标下一个是否还有,如果没有证明链表遍历完毕 while(pre.next != null){ //判断当前节点的值和下一个节点的值是否相等 if(pre.val == pre.next.val ){ //如果相等则将当前值的下一个指向,指向当前节点的下下一个,也就是说如果原来当前节点1指向2,2指向3, //那么现在1直接指向3,把中间的2去掉,因为2和1的值是相等的 pre.next = pre.next.next; }else{ //如果不相等,则将pre指向下一个节点。 pre = pre.next; } } return head; } }
复杂度分析
时间复杂度:O(n),其中 n 是链表的长度。
空间复杂度:O(1)。