注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex82 Remove Duplicates from Sorted List II  

2015-05-15 22:08:38|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


把所有重复过的元素都删掉,比以前那个Remove Duplicates from Sorted List难一些,好在想到一种好的技术,在head前面加一个元素,这样就不用担心head没有前缀节点的问题了,直接遍历一遍,删除完毕。

bool traverse(struct ListNode*head,int val)
{
//判定当前节点是否有重复
//如果有重复,就把后面的重复节点删除
//然后返回true,退出后再删当前节点
struct ListNode * current, *p = NULL;
current = head;

int deleteVal = val;
bool del = false;
while (current->next != NULL&&current->next->val == val)
{
del = true;
p = current->next;

current->next = p->next;
free(p);
p = NULL;

}
return del;//这个表示有没有重复的
}

struct ListNode* deleteDuplicates(struct ListNode* head)
{
struct ListNode * current, *p = NULL;
if (head == NULL)
return NULL;

// 在head前面添加一个INT_MIN的值,这样就可以避免一直删head的问题
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = INT_MIN;
p->next = head;
head = p;

current = head;
int val = current->val;
bool mark;

while (current->next!=NULL&&current->next->next != NULL)
{
val = current->next->val;
// 查找下一节点的值
//搜索 current->next之后的节点是否和current->next节点值一样
mark = traverse(current->next, val);
//如果一样的话就要删除current->next节点
if (mark) //删除current->next节点
{
p = current->next;
current->next = p->next;
free(p);
p = NULL;
}
else
{
//current->next是单节点,直接过去
current = current->next;
}

}

p = head;
head = head->next;
free(p);
p = NULL;
return head;
}

second time,精简代码 c++实现

// 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 == NULL) return head;
ListNode *current, *tmp;

tmp = new ListNode(INT_MAX); // fake head
tmp->next = head;
head = tmp;

current = head;
bool flag = false;
while (current&&current->next)
{
flag = false;
while (current->next->next&&current->next->val == current->next->next->val)
{
tmp = current->next->next;
current->next->next = tmp->next;
flag = true;
delete tmp;
tmp = NULL;
}
if (flag)
{
tmp = current->next;
current->next = tmp->next;
delete tmp;
tmp = NULL;
}
else current = current->next;
}
//delete fake head;
tmp = head;
head = head->next;
delete tmp;
tmp = NULL;
return head;
}
};

java version 2015/12/3

public class RemoveDuplicatesfromSortedListII {
public ListNode deleteDuplicates(ListNode head) {
return helper(head);
}
private ListNode helper(ListNode head) {
ListNode current = new ListNode(Integer.MAX_VALUE);
current.next = head;
head = current;
ListNode p = null;
int last = 0;
boolean flag = false;
while (current != null && current.next != null) {
p = current.next;
last = p.val;
flag = false; // 是否有重复元素的标记
while (p != null && p.next != null && p.val == p.next.val) {
p = p.next;
flag = true;
}
if (flag) {
// 如果有重复元素的话,current的位置是不用改变的
current.next = p.next;
} else {
current.next = p;
current = current.next;
}
}
return head.next;
}
}


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017