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/
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權,非商業(yè)轉載請注明出處权悟。
-
1.常規(guī)解法
思路:
1.遍歷該鏈表,如果 cur.val == cur.next.val推盛,則刪除掉重復元素
2.如果 cur.val 峦阁!= cur.next.val,則將節(jié)點向后移動一位
3.那么當到最后一個節(jié)點時耘成,就可以刪除掉重復元素了
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節(jié)點指向的元素,同時將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.假設頭節(jié)點之后的節(jié)點都是沒有重復的疆栏,那個我們只需判斷 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
-
源碼
-
我會隨時更新新的算法许蓖,并盡可能嘗試不同解法,如果發(fā)現問題請指正
- Github