Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given1->2->3->3->4->4->5 , return 1->2->5 .
Given1->1->1->2->3 , return 2->3 .
<Solution>Given
Given
這題是 Remove Duplicates from Sorted List 的衍生題
是要把所有重複的 node 都拿掉,而不是只留一個
還是在考 link list 的操作,這題因為會有刪除所有 node 的情況出現
用一個 dummy head 配合兩個指針,會比較好寫
code 如下
c++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for singly-linked list. | |
* struct ListNode { | |
* int val; | |
* ListNode *next; | |
* ListNode(int x) : val(x), next(NULL) {} | |
* }; | |
*/ | |
class Solution { | |
public: | |
ListNode* deleteDuplicates(ListNode* head) { | |
if(!head || !head->next) { | |
return head; | |
} | |
ListNode *dummy = new ListNode(0); | |
dummy->next = head; | |
ListNode *prv = dummy; | |
ListNode *cur = NULL; | |
while(prv->next) { | |
cur = prv->next; | |
while(cur->next && cur->next->val == cur->val) { | |
cur = cur->next; | |
} | |
if(cur != prv->next) { | |
prv->next = cur->next; | |
} | |
else { | |
prv = prv->next; | |
} | |
} | |
return dummy->next; | |
} | |
}; |
kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Example: | |
* var li = ListNode(5) | |
* var v = li.`val` | |
* Definition for singly-linked list. | |
* class ListNode(var `val`: Int) { | |
* var next: ListNode? = null | |
* } | |
*/ | |
class Solution { | |
fun deleteDuplicates(head: ListNode?): ListNode? { | |
return if(head == null || head.next == null) { | |
head | |
} else { | |
val dummy = ListNode(0) | |
dummy.next = head | |
var prv: ListNode? = dummy | |
var cur: ListNode? = null | |
while(prv?.next != null) { | |
cur = prv!!.next | |
while(cur?.next != null && cur!!.`val` == cur!!.next.`val`) { | |
cur = cur.next | |
} | |
if(cur != prv!!.next) { | |
prv!!.next = cur?.next | |
} else { | |
prv = prv?.next | |
} | |
} | |
dummy.next | |
} | |
} | |
} |
沒有留言:
張貼留言