问题描述
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
解决思路
不断的比较当前节点与前一个节点和下一个节点的值，若相等，则往后移动；不想等，设为realNode
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode dummy = new ListNode(0);
ListNode preNode = dummy;
ListNode curNode = head;
ListNode realNode = dummy;
while(curNode != null){
if((preNode == dummy || preNode.val != curNode.val) && (curNode.next == null || curNode.val != curNode.next.val)){
realNode.next = curNode;
realNode = curNode;
}
preNode = curNode;
curNode = curNode.next;
preNode.next = null;
}
return dummy.next;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
