RemoveDuplicatesFromSortedListII [source code]
public class RemoveDuplicatesFromSortedListII {
static
/******************************************************************************/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode (0);
dummy.next = head;
ListNode cur = dummy, res = head;
while (cur.next != null) {
ListNode fast = cur;
int count = 0;
while (fast.next != null && fast.next.val == cur.next.val) {
count++;
fast = fast.next;
}
if (count > 1) {
cur.next = fast.next;
fast.next = null;
} else {
cur = fast;
}
}
return dummy.next;
}
}
/******************************************************************************/
public static void main(String[] args) {
RemoveDuplicatesFromSortedListII.Solution tester = new RemoveDuplicatesFromSortedListII.Solution();
}
}
一开始写的这个:
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode (0);
dummy.next = head;
ListNode write = dummy, read = head;
while (read != null) {
if (write == dummy || write.val != read.val) {
write = write.next;
write.val = read.val;
}
read = read.next;
}
write.next = null;
return dummy.next;
}
}
然后发现理解错题目了, 这个题目不是去重, 而是把有重复的全都删了; 顺便, 上面的代码的一个技巧就是, write应该是一个inclusive的, 不然最后需要砍断的时候, 你可能在write.next的位置, 就没有办法砍断了;
不过这里这个delete的思路其实也不难; 具体可以有两种思路, 一种是用awice那种anchor的思路, 一种就是我自己经常用的探脚的思路; 好久没有用伸脚思路了, 这里写一次;
但是写了一下, 感觉伸脚思路不是很好写, 比如0 1a 1b 1c 2a 2b 2c这样一个list, 比如我要删1的时候, 我慢指针应该站在0这个类似prev的位置上面, 然后fast找到了1c, 然后你下面把cur放在哪里? 如果让0接管2a, 然后1c.next = null (防止内存泄露), 那么你cur肯定不能站在1c, which is the prev of all 2s; 好像也不是不可以, 尝试一下; 反正这个问题如果:
- 用anchor, 那么肯定没有, 删2的时候直接站在1a, 一点问题都没有;
- 不管内存泄露, 也没有问题, 0.next = 2a之后cur直接走到1c, 继续;
最后没有用anchor做出来了; 后来想了想, 好像这题用anchor也未必就好写, 因为毕竟是LinkedList, 还是需要知道parent的, 站在prev的位置上面比较有优势;
速度是1ms (13%). 唯一的一个bug: 就是最外面这个header, 一开始写的是cur != null, 但是这个是不对的, 应该用cur.next != null; 这个的理由并不是什么很简单的pre leaf的论断, 而是因为这个算法你自己画一个trace就知道了, 如果不判断next, 最后就没有办法terminate;
整个算法的结构有点类似conditional increment的思路;
比较难的一个思路这里用fast.next而不是fast来探路, 因为我们最后找到末尾的时候, 我们想要的是duplicate run的end, 而不是下一个数字run的开头;
没有editorial;
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return null;
ListNode FakeHead=new ListNode(0);
FakeHead.next=head;
ListNode pre=FakeHead;
ListNode cur=head;
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
if(pre.next==cur){
pre=pre.next;
}
else{
pre.next=cur.next;
}
cur=cur.next;
}
return FakeHead.next;
}
大概脑子里想了一下, 还是能理解的; 这个其实就是anchor的思路, 不过因为是一个LinkedList题目, 就算是anchor思路, anchor的其实也是prev; 然后注意他找run end的时候, 他也是停在end;
Actually I found there is a more straightforward way to solve this problem:
https://discuss.leetcode.com/topic/61919/o-n-time-o-1-space-easiest-understanding
The idea is simple, we maintain two pointers, pre, cur in the given List. Pre pointer is always referring to one position before the cur pointer. When we found pre.val != cur.val && cur.val != cur.next.val, the node referred by cur pointer is a unique node.
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0 == head.val ? 1 : 0);// to guarantee the dummy node is not same as the original head.
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
ListNode first = dummy; // the first node in the new unduplicated(result) list.
while (cur != null && cur.next != null) {
if (cur.val != pre.val && cur.val != cur.next.val) { // we found a unique node, we connect it at the tail of the unduplicated list, and update the first node.
first.next = cur;
first = first.next;
}
pre = cur;
cur = cur.next;
}
if (pre.val != cur.val) { // the last node needs to be dealt with independently
first.next = cur;
first = first.next;
}
first.next = null; // the subsequent list is duplicate.
return dummy.next;
}
大概画了一个trace之后才理解这个算法, 完全不straightforward, 还有许多的特殊情况处理;
不过可以学习的一个思路是, 在这种modify LinkedList的题目当中, 一个可以适当降低难度的思路就是collect on the side, 也就是用另外的一个list(head node)来收集, 而不是直接在当前的list上面修改; 这个思路的好处是有时候可能适当降低思维难度, 坏处是不是InPlace, 所以如果题目要求InPlace, 那就不对了: 改参数指针是没用的, 指针是pass by value;
Share my solution using one loop:
Look at this example:
{1,1,1,2,2,3,4}
- Make a dummy node before 1.
{0,1,1,1,2,2,3,4}
pre:0
cur:1- Move cur until value of cur != cur.next
Now cur stops at the first 2
Using repeat to indicate if jumping from a repeated number.
Here repeat is true, so we only let pre.next point to 2- Keep moving cur, it will stops at 3.
Now the repeat is still true, so we let pre.next point to 3
This also means that 1,1,1,2,2 has been by passed. since pre.next is also dummy.next- we keep moving, now cur is at 4
Now finally the repeat is false, we can move pre to pre.next(from dummy move to 3)- loop end, because we don’t touch 3.next, it will still be 4
So the answer is 3,4
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = head;
boolean repeat = false;
while(cur.next != null){
if(cur.val == cur.next.val){
repeat = true;
cur = cur.next;
} else {
cur = cur.next;
if(!repeat){
pre = pre.next;
}
pre.next = cur;
repeat = false;
}
}
if(repeat) pre.next = null;
return dummy.next;
}
pretty easy recursive solution!!!
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null||head.next==null) return head;
if(head.val!=head.next.val){
head.next=deleteDuplicates(head.next);
return head;
}
else{
while(head.next!=null&&head.val==head.next.val)
head=head.next;
return deleteDuplicates(head.next);
}
}
}
这个算法的设计其实还是很合理的; 反正, recursion算法, 尤其是LinkedList的recursion算法, 关键就是设计好root level decision, 也就是假设你可以通过返回值的方式获得下面的正确结果. 不过这题的这个root level decision其实不是完全那么简单; 他这里处理的还是比较好的, 最后实际上纠结的就是你到底是否在本level的返回值里面包含head; 如果有duplicate, 那么肯定就不包含了;
public ListNode deleteDuplicates(ListNode head) {
ListNode temp=new ListNode(0);
temp.next=head;
ListNode sec=temp;
while(sec.next!=null && sec.next.next!=null){
if(sec.next.val==sec.next.next.val){
int dupli=sec.next.val;
while(sec.next!=null && sec.next.val==dupli){
sec.next=sec.next.next;
}
}
else {
sec=sec.next;
}
}
return temp.next;
}
这个算法反正基本也是差不多, 也是站在duplicate之前的一个位置, 然后skip;
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
if current node is not unique, return deleteDuplicates with head.next.
If current node is unique, link it to the result of next list made by recursive call. Any improvement?
这个就是上一个说过的那个recursion的做法, 还是挺有意思的;
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
//use two pointers, slow - track the node before the dup nodes,
// fast - to find the last node of dups.
ListNode dummy = new ListNode(0), fast = head, slow = dummy;
slow.next = fast;
while(fast != null) {
while (fast.next != null && fast.val == fast.next.val) {
fast = fast.next; //while loop to find the last node of the dups.
}
if (slow.next != fast) { //duplicates detected.
slow.next = fast.next; //remove the dups.
fast = slow.next; //reposition the fast pointer.
} else { //no dup, move down both pointer.
slow = slow.next;
fast = fast.next;
}
}
return dummy.next;
}
}
below is my solution without dummy node, almost the same:
ListNode pre = null;
ListNode cur = head;
while(cur != null && cur.next != null){
if(cur.val != cur.next.val){
pre = cur;
cur = cur.next;
}else{
while(cur.next != null && cur.next.val == cur.val){
cur = cur.next;
}
if(pre != null){
pre.next = cur.next;
}else{
head = cur.next;
}
cur = cur.next;
}
}
return head;
不用dummy的解法; 还可以; 思路其实就是一个对Null的特殊判断; 反正最后肯定是有一个head的; 在某一个位置给head重新负值就行了;
submission基本波动;
Problem Description
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.
Difficulty:Medium
Total Accepted:128K
Total Submissions:428.3K
Contributor:LeetCode
Related Topics
linked list