83. 删除排序链表中的重复元素
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
-
1.常规解法
思路:
1.遍历该链表,如果 cur.val == cur.next.val,则删除掉重复元素
2.如果 cur.val != cur.next.val,则将节点向后移动一位
3.那么当到最后一个节点时,就可以删除掉重复元素了
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
//用于测试用例
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
public static ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
复杂度分析:
时间复杂度:O(n),假设 n 是列表的长度,那么时间复杂度为 O(n)。
空间复杂度:O(1)
-
2.快慢指针法
思路:
1.初始化两个指针,一个慢指针slow指向head, 而快指针fast指向head.next
2.当slow.var == fast.var 时,删除掉当前fast节点指向的元素,同时将fast向后移
3.当slow.var != fast,var 时,同时将两个指针向后移动一位
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
if (fast.val != slow.val) {
fast = fast.next;
slow = slow.next;
} else {
slow.next = fast.next;
fast = fast.next;
}
}
return head;
}
复杂度分析:
时间复杂度:O(n)
空间复杂度:O(1)
-
3.递归法
思路:
1.假设头节点之后的节点都是没有重复的,那个我们只需判断 head.next.val 和 head.val 值是否相同
2.如果相同,返回 head.next,不同返回 head即可
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n),由于使用了递归,将会使用隐式栈空间,递归深度可能会达到n层
-
测试用例
public static void main(String[] args) {
int[] arr = new int[] {1, 1, 2, 3, 3, 4};
ListNode listNode = new ListNode(arr);
System.out.println(listNode);
System.out.println("删除链表中的重复元素" + deleteDuplicates3(listNode));
}
-
结果
1->1->2->3->3->4->NULL
删除链表中的重复元素1->2->3->3->4->NULL
-
源码
-
我会随时更新新的算法,并尽可能尝试不同解法,如果发现问题请指正
- Github