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
.
给一个链表,把其中所有的有相同重复的项都给删除了。
1 首先按照自己的习惯,想了想主要部分思路。cur检查当前的,next检查下一部分的;碰到next==cur的时候,不做操作,继续检查;碰到next!=cur的时候,需要有个识别器,cur之前有重复吗?有重复的话,继续把next作为cur,重新处理;没有重复的话,可以算作新的结点。大致思路有了,但是问题是头结点的部分怎么办?感觉要个别处理了。于是修改了很多,accept了,但是如下面看到的,非常不优雅!
if(head == null || head.next == null){ return head; } ListNode cur = head; boolean dup = false; //头节点处理部分 while(cur.next!=null){ ListNode next = cur.next; if(next.val!=cur.val&&dup==true){ cur=next; dup=false; head =cur; continue; } if(next.val!=cur.val&&dup==false){ head = cur; cur = next; dup = false; break; } cur =next; dup=true; } if(dup==true && cur.next==null){ return null; } if(head.next==null){ return head; } //头节点找到后,后面部分处理 dup=false; ListNode newnode =head; while(cur.next!=null){ ListNode next = cur.next; if(next.val==cur.val){ dup=true; cur=cur.next; continue; } else{ if(dup==true){ cur=next; dup=false; continue; } else{ newnode.next=cur; newnode=newnode.next; cur=cur.next; continue; } } }
if(dup==false){ newnode.next=cur; } else{ newnode.next=null; } return head;
2( 前面的代码不用细看)之后参考了大牛的代码,http://blog.csdn.net/fightforyourdream/article/details/15024517,原来还有虚拟表头的用法。想到之前做题目经常会遇到因为head部分和body部分不同,而要写两端相似的代码情况。看来虚拟表头是一个不错的武器,入库,重写!
前半部分修改成
ListNode dummyhead = new ListNode(Integer.MIN_VALUE); dummyhead.next = head; ListNode cur = head; boolean dup = false; ListNode newnode =dummyhead;
最后返回
return dummyhead.next;
能通过,太爽了~果然最优美的就是最简洁的。
3 但是细看大牛的写法还是比我代码更少,去研究了它的主要部分思想。用了3个节点,pre, cur, next ,其中pre 相当于我的newnode,就是最后要加入进去的部分。逻辑上面也更加清楚。继续把自己核心代码改写一下:
while(next!=null){ if(next.val!=cur.val){ if(dup){ newnode.next=next; dup=false; } else{ newnode.next=cur; newnode=newnode.next; } cur=next; next=next.next; } else{ dup=true; next =next.next; } }
代码量小了很多,也更加直观;这里我用newnode的方式,我觉得要比pre更加清晰一点。