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

HT·生活

123

 
 
 

日志

 
 

ex86 Partition List  

2015-05-17 20:15:34|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.


这个题目很诡异,它加的那个限制条件——保持原有顺序,其实还降低了它的难度,开始的时候用来插入排序,后来发现破环原有的顺序了。仔细考虑一下,完全直接压栈就可以了。见c代码,开始用了两个链表,一个用来压栈,和另一个最后的时候拼接起来,

struct ListNode* partition(struct ListNode* head, int x) {
if (head == NULL)
return NULL;
struct ListNode*current = NULL, *tail = NULL, *head1 = NULL, *p = NULL,*p1=NULL,*p2=NULL;

p = (struct ListNode*)malloc(sizeof(struct ListNode*));
p->val = INT_MAX;
p->next = head;
head = p; //给了一个虚拟的头


p1 = (struct ListNode*)malloc(sizeof(struct ListNode*));
p1->val = INT_MIN;
p1->next =NULL;
head1 = p1; //给了一个虚拟的头

current = head;

tail = head1;
while (current!=NULL&&current->next!=NULL)
{
if (current->next->val < x)
{
//需要插入到第一条链表之中
p1 = current->next;
p2 = p1->next; //把要挪到前面的点都拆出来
current->next = p2;
p1->next = NULL; //把p1点拆出来

tail->next = p1;
tail = tail->next;
//因为要保持他们的原始顺序不变,这个地方就不必用插入排序了
}
else
{
current = current->next;
}
}

p1 = head1;
head1 = head1->next;
//free(p1);
//p1 = NULL;

p = head;
head = head->next;
//free(p);
//p = NULL;//内存回收
if (head1 == NULL)
{
return head;
}
tail->next = head;

return head1;

}

update java version 2015/12/7

import ht.ListNode;
public class PartitionList {
public ListNode partition(ListNode head, int x) {
return helper(head, x);
}
private ListNode helper(ListNode head, int x) {
ListNode fake = new ListNode(x);
ListNode tail = fake;

ListNode current = new ListNode(Integer.MIN_VALUE);
current.next = head;
head = current;
current = head;
while (current != null && current.next != null) {
if (current.next.val < x) {
current = current.next;
} else {
tail.next = current.next;
tail = tail.next;
current.next = current.next.next;
}
}
tail.next = null;
current.next = fake.next;
return head.next;
}
}


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

历史上的今天

评论

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

页脚

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