找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1302|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Partition List】-【刷题第一弹2014】

[复制链接]

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 10-22-2014 05:28 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:https://oj.leetcode.com/problems/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.

思路:

用一个head指针来记录前边小于x的list的尾node, prev为被检测节点的前一个,如果被检测结点value小于x,则将其查到head后边。注意开始在原list前加个dummy,方便操作

  1.     ListNode *partition(ListNode *head, int x) {
  2.         ListNode dummy(-1);
  3.         dummy.next = head;
  4.         head = &dummy;
  5.         for (ListNode* prev = &dummy; prev->next ;)
  6.         {
  7.             ListNode* cur = prev->next;
  8.             if (cur->val < x) {
  9.                 if (prev == head)
  10.                     prev = prev->next;
  11.                 else {
  12.                     prev->next = cur->next;
  13.                     cur->next = head->next;
  14.                     head->next = cur;   
  15.                 }

  16.                 head = head->next;
  17.                
  18.             } else {
  19.                 prev = prev->next;
  20.             }
  21.         }
  22.         
  23.         return dummy.next;
  24.     }
复制代码

时间复杂度:O(n)

空间复杂度:O(1)




本帖被以下淘专辑推荐:

23

主题

5

精华

211

积分

高级会员

Rank: 3Rank: 3

积分
211
发表于 2-16-2015 12:01 AM | 显示全部楼层
贴一个java版本的
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) {
  7. *         val = x;
  8. *         next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     public ListNode partition(ListNode head, int x){
  14.         ListNode dummy1 = new ListNode(-1);
  15.         ListNode dummy2 = new ListNode(-1);
  16.         ListNode list1 = dummy1;
  17.         ListNode list2 = dummy2;

  18.         if (head == null || head.next == null){
  19.             return head;
  20.         }
  21.         
  22.         while(head != null){
  23.             if (head.val < x){
  24.                 list1.next = head;
  25.                 list1 = list1.next;
  26.             }
  27.             else{
  28.                 list2.next = head;
  29.                 list2 = list2.next;
  30.             }
  31.             head = head.next;
  32.         }
  33.         
  34.         list2.next = null;
  35.         list1.next = dummy2.next;
  36.         return dummy1.next;
  37.     }
  38.    
  39. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表