首页 > 其他 > 详细

[LeetCode 86] Partition List

时间:2015-03-27 17:23:35      阅读:200      评论:0      收藏:0      [点我收藏+]

题目链接:partition-list


/**
 * 
	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.
	
	Hide Tags
 *
 */

public class PartitionList {

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
//	166 / 166 test cases passed.
//	Status: Accepted
//	Runtime: 288 ms
//	Submitted: 1 minute ago
	
	//设置两个链表,小于x的节点按顺序链接到less尾部中,大于或等于的节点按顺序链接到greater尾部
	//时间复杂度o(n),空间复杂度 o(1)
    public ListNode partition(ListNode head, int x) {    	
        ListNode less = new ListNode(Integer.MAX_VALUE);
        ListNode greater = new ListNode(Integer.MAX_VALUE);
        ListNode cur1 = less;
        ListNode cur2 = greater;        
        while(head != null) {        	
        	if(head.val < x) {
        		cur1.next = head;
        		cur1 = cur1.next;
        	} else {
				cur2.next = head;
				cur2 = cur2.next;
			}
        	head = head.next;
        }
        cur2.next = null;
        cur1.next = greater.next;        
        return less.next;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}


[LeetCode 86] Partition List

原文:http://blog.csdn.net/ever223/article/details/44678957

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!