# How can i improve my code??

• I m using an array to store the number of occurrences of each element,i have taken assumption dat elements are less than 100 and greater than -100

``````    int A[200]={0};
while(temp)
{
if(temp->val<0)
A[temp->val+200]++;//if element is negative then add size of array to it
else              //so that index always remain positive
A[temp->val]++;
temp=temp->next;
}
while(temp)
{
if((temp->val<0 && A[temp->val+200]>1)||(temp->val>=0&&A[temp->val]>1))
{
free(temp);
}
else
{               //otherwise just delete temp
prev->next=temp->next;
free(temp);
temp=prev->next;
}
}
else
{
prev=temp;
temp=temp->next;
}
}
``````

it takes O(n) for both running time n space.

• This post is deleted!

• There is no need to keep track of all distinct elements in the list. My code is in python. It only runs through the list once and needs constant space.

{

``````    result=None

while(p0.next!=None):
# the last two nodes
if (p0.next.next==None):
if (p0.val == p0.next.val):
if (p0!=p1):
p1.next =None
else:
p1.next = p0.next
p1 = p1.next
# if result not initialized
if (result==None):
result =p1

# in the middle
elif (p0.val < p0.next.val):
if (p0.next.val<p0.next.next.val):
p1.next = p0.next
p1 = p1.next
# if result not initialized
if(result==None):
result = p1

p0=p0.next

return result
``````

}

• yes u r correct
i actually didnt considered dat list is sorted

• Use a duplicate count and move into the final list.

``````public class Solution {

ListNode prev = null;
int dupCount = 0;
while (null != ptr)
{
// current matches the next, increase count and move to next
if (null != ptr.next && ptr.val == ptr.next.val)
dupCount++;
else
{
// no dup found, need to move into final list
if (0 == dupCount)
{
// first time, set up new head
if (null == prev)
else
{
prev.next = ptr;
prev = ptr;
}
}
// onto next different node, reset dupCount
dupCount = 0;
}
ptr = ptr.next;
}

// terminate the rest of the list if any
if (null != prev)
prev.next = null;

}
``````

}

• Here is my accepted code in python, O(n) with constant space complexity:

``````class Solution:
# @return a ListNode

return None

head2 = None  # the first element of the new list
cur2 = None  # keep track of the latest element of the new list

wrong_value = None # record the duplicate value

while cur is not None:
if cur.val>pre.val: # check if the previous value should be added
if pre.val!=wrong_value:
else:
cur2.next = ListNode(pre.val)
cur2 = cur2.next
else:
wrong_value = cur.val

pre = cur
cur = cur.next

if pre.val!=wrong_value: # we haven't checked the last one element of origin list
if cur2 is not None:
cur2.next = ListNode(pre.val)
else: # head2 is Null if all the previous elements are duplicate

``````

Basically, we record the duplicate value when the value of current node is same with the previous one. When we proceed to a new value, we check if the previous value is fine to be added to the new list. I think it's a rather straight-forward solution to me.

• here is my java solution,O(n) and constant space:

``````public ListNode deleteDuplicates(ListNode head) {
ListNode root = new ListNode(0);
ListNode lastValidate = root,pre = head;
}
}
}else{
lastValidate = pre;
}
}
return root.next;
}``````

• This post is deleted!

• Here's my answer. I think the basic idea is the same.........Draw graph. Use prev, cur and end to traverse the list, and use a flag dup to record whether there are dup nodes.......

/**

• struct ListNode {

• ``````int val;
``````
• ``````ListNode *next;
``````
• ``````ListNode(int x) : val(x), next(NULL) {}
``````
• };
*/
class Solution {
public:
ListNode *dummy = new ListNode(0);

`````` dummy->next = head;
ListNode *prev=dummy;

int dup = 0;
for(ListNode *cur = head, *end=cur->next; cur!=NULL,end!=NULL; ){
if (cur->val == end->val){
end = end->next;
dup=1;
continue;
}
if(dup){
prev->next=end;
cur = end;
end=cur->next;
dup=0;
}
else{
prev = cur;
end = end->next;
cur = cur->next;
}

}

if (dup){
prev->next = NULL;
}

return dummy->next;
``````
``````}
``````

};

• Here's my answer. I think the basic idea is the same.........Draw graph. Use prev, cur and end to traverse the list, and use a flag dup to record whether there are dup nodes.......

``````/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */

ListNode *prev=dummy;

int dup = 0;
for(ListNode *cur = head, *end=cur->next; cur!=NULL,end!=NULL; ){
if (cur->val == end->val){
end = end->next;
dup=1;
continue;
}
if(dup){
prev->next=end;
cur = end;
end=cur->next;
dup=0;
}
else{
prev = cur;
end = end->next;
cur = cur->next;
}

}

if (dup){
prev->next = NULL;
}

return dummy->next;

}

};
``````

• Here is my answer, When decide whether add the node to the result list or not, i use another point to find the lenght of sublist which has the same val.if the length is 1,then add the node to result list.

``````public ListNode deleteDuplicates(ListNode head) {
ListNode suc = null;
cur = cur.next;
cur.next = null;
}
}

}``````

• Shall we concern about memory leaks problem? You just ignore the duplicate members.

• Using java,the gc will recycle the unused memory using gc algorithm.

• O(n) solution using simple linked list traversal and it takes constant space, Space Complexity O(1) Time Complexity O(n).

``````  public class Solution {

while( p!= null && p.next != null){
if(p.val == p.next.val){
p.next = p.next.next;
}else{
p = p.next;
}
}

}
}``````

• maybe you put the ans in the wrong place

• Here is my answer. Instead of using a duplicate count, I'm using a boolean to determine whether a number is repeated.

``````public class Solution {
if (head == null) return null;

boolean rep = false;
ListNode cur = new ListNode(0);
while (cur.next != null && cur.next.next!= null) {
if (cur.next.val == cur.next.next.val) {
cur.next = cur.next.next;
rep = true;
}
else
{
if (rep) {
cur.next = cur.next.next;
rep = false;
} else {
cur= cur.next;
}
}
}
if (rep) cur.next = cur.next.next;
}
``````

}

• since list is sorted, compare adjacent nodes seems enough...

``````class Solution {
public:
for(ListNode *p = 0, *q = head; q; ){
ListNode *r = q;
while(r->next && r->next->val == q->val){
r = r->next;
}
if(q == r){ // q is distinct
p = q;
}
else{ // q ~ r are duplicates
(p ? p->next : head) = r->next;
}
q = r->next;
}
}
};``````

• I think we should!

• Here's my code. The idea is to use two pointers. One points to the latest stable (or final) result, the other points to the node we're going to compare in next iteration.

Here's the C# code

``````public ListNode DeleteDuplicates(ListNode head) {

}

int value = stableNode.next.val;
ListNode current = stableNode.next.next;

while(current != null) {
// same value as previous one. remove all nodes.
if (current.val == value) {
stableNode.next = null;
}
else { // we see a different node.
if (stableNode.next != null) { // in this case, stableNode.next is stable result, move one step
stableNode = stableNode.next;
}

stableNode.next = current;
value = current.val;
}

current = current.next;
}