首页 > 代码库 > Leetcode: Remove Duplicates from Sorted List

Leetcode: Remove Duplicates from Sorted List

遇到的问题:input{1,1,1}, output{1,1}, expected{1}, 原因在于若temp.val==temp.next.val, 则需要temp.next=temp.next.next, 这时候就不要temp=temp.next了

注意停止条件不光是temp!=null,还应该有temp.next!=null

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode deleteDuplicates(ListNode head) {
14         if(head==null) return null;
15         ListNode temp=head;
16         while(temp!=null && temp.next!=null){
17             if(temp.val==temp.next.val){
18                 temp.next=temp.next.next;
19             }
20             else temp=temp.next;
21         }
22         return head;
23     }
24 }

别人的solution:

Solution1: (未研究,感觉比我的复杂)

 1 public class Solution {
 2     public ListNode deleteDuplicates(ListNode head) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if(head == null)    // we can otherwise use dummy node instead. But
 6             return null;    // be careful about the value you put in the dummy node.
 7         
 8         ListNode currentNode = head;
 9         while(currentNode.next!=null){
10             ListNode p = currentNode.next;
11             while(p!=null && p.val==currentNode.val)
12                 p = p.next;
13             if(p == null){
14                 currentNode.next =null;
15                 break;
16             }
17             currentNode.next = p;
18             currentNode = p;
19         }
20         return head;
21     }
22 }

Solution 2: Runner Technique(未研究,感觉是好的切入点,但是比我的复杂)

 1 public class RemoveDuplicatesFromSortedList {
 2     public ListNode deleteDuplicates(ListNode head) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if (head == null) {
 6             return null;
 7         }
 8         if (head.next == null) {
 9             return head;
10         }
11         ListNode saveHead = head;
12         ListNode runner = head;
13 
14         while (runner.next != null) {
15             if (runner.val != runner.next.val && runner.val != saveHead.val) {
16                 head.next = new ListNode(runner.val);
17                 head = head.next;
18             }
19             runner = runner.next;
20         }
21         if (runner.val != saveHead.val) {
22             head.next = new ListNode(runner.val);
23             head = head.next;
24             head.next = null;
25         } else {
26             head.next = null;
27         }
28         return saveHead;
29 
30     }
31 }