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
.
A:
-------------------------4th pass --------用递归的思想做的-------
public class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null) return head; if(head.val == head.next.val){ int findVal = head.val; while(head !=null && head.val == findVal) head=head.next; return deleteDuplicates(head); }else{ head.next = deleteDuplicates(head.next); return head; } } }
--------------------3 rd Pass ------------------ 一遍AC ,不错----------------------
public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode header = new ListNode(0); header.next = head; ListNode preNode = header; // pre node ListNode curNode = head; // current node while(curNode!= null && curNode.next != null){ if(curNode.val == curNode.next.val){ // delete all values that int value = curNode.val; while(preNode.next != null && preNode.next.val == value){ preNode.next = preNode.next.next; } curNode=preNode.next; }else{ preNode = preNode.next; curNode = curNode.next; } } return header.next; } }
-------------------------------第二遍---------------------------
思路就是,各自用两个header, 旧的每次取下第一个,记录下value,查看下面的是否相同,并设置一个boolean 标记。 然后add 到新list 的tail上去。
public class Solution { public ListNode deleteDuplicates(ListNode head) { // build another list, and move only those with no ducplicats ListNode header1 = new ListNode(0); header1.next = head; ListNode header = new ListNode(0); ListNode tail =header; int oldVal; boolean findDuplicate; while(header1.next!= null){ if( header1.next.next == null ){ // if only one node left tail.next = header1.next; tail =tail.next; break; } oldVal = header1.next.val; findDuplicate = false; ListNode tmpNode = header1.next; header1.next = header1.next.next; //delete the first node while(header1.next != null && header1.next.val == oldVal){ //delete first node in header1 list findDuplicate = true; header1.next = header1.next.next; } if( ! findDuplicate){ tail.next = tmpNode; tail = tail.next; } } // set tail.next as null tail.next = null; return header.next; } }
--------------------1st --------每次detach head, 然后加到结果的tail 上。---------------- -----------------
public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode header = new ListNode(0),tail = header; while(head != null){ // delete all the duplicate node if(head.next ==null || head.val != head.next.val){ //detach the head tail.next = head; tail = tail.next; head = head.next; tail.next = null; }else{ // delete all nodes with the same value of node int duplicateVal = head.val; while(head!=null && head.val == duplicateVal) head = head.next; } } return header.next; } }
No comments:
Post a Comment