首页 > 代码库 > 82. Remove Duplicates from Sorted List II

82. Remove Duplicates from Sorted List II

2024-09-30 13:40:02   219人阅读

题目：

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

链接： http://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

6/3/2017

思路：遍历list，如果有重复则置delete，同时while loop直到下一个不同的元素，重置delete，更新prev.next。因为无法判断下一个元素是否是重复的，所以不更新prev。

如果cur是distinct，那么更新prev为cur，继续前面的过程。

注意的问题：

1. 用delete显示是否应该删除cur

2. 内循环和第25行完全去除了duplicate

3. 只有在cur是distinct的时候更新prev，见第29行

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode deleteDuplicates(ListNode head) {
11         if (head == null) {
12             return head;
13         }
14         boolean delete = false;
15         ListNode dummy = new ListNode(0);
16         ListNode prev = dummy;
17         dummy.next = head;
18         ListNode cur = head;
19         while (prev.next != null) {
20             while (cur != null && cur.next != null && cur.val == cur.next.val) {
21                 delete = true;
22                 cur.next = cur.next.next;
23             }
24             if (delete) {
25                 prev.next = cur.next;
26                 cur = prev.next;
27                 delete = false;
28             } else {
29                 prev = cur;
30                 cur = prev.next;
31             }
32         }
33         return dummy.next;
34     }
35 }

别人的答案：

不需要delete的方法，通过prev.next == cur来判断的，注意其实第9行也有不同，内循环每次更新cur而不是cur.next

https://discuss.leetcode.com/topic/3890/my-accepted-java-code

 1 public ListNode deleteDuplicates(ListNode head) {
 2         if(head==null) return null;
 3         ListNode FakeHead=new ListNode(0);
 4         FakeHead.next=head;
 5         ListNode pre=FakeHead;
 6         ListNode cur=head;
 7         while(cur!=null){
 8             while(cur.next!=null&&cur.val==cur.next.val){
 9                 cur=cur.next;
10             }
11             if(pre.next==cur){
12                 pre=pre.next;
13             }
14             else{
15                 pre.next=cur.next;
16             }
17             cur=cur.next;
18         }
19         return FakeHead.next;
20     }

递归写法，不建议，但是是一种思路

https://discuss.leetcode.com/topic/5206/my-recursive-java-solution

更多讨论：

https://discuss.leetcode.com/category/90/remove-duplicates-from-sorted-list-ii

82. Remove Duplicates from Sorted List II


联系
我们