LeetCode Online Judge 题目C# 练习 - 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.

 1 　　　　 public static LinkedListNode PartitionList(LinkedListNode head, int x)
 2         {
 3             if (head == null)
 4                 return null;
 5 
 6             LinkedListNode ret = new LinkedListNode(); 
 7             LinkedListNode retcurr = ret;
 8             LinkedListNode curr = head;
 9 
10             while (curr != null)
11             {
12                 if ((int)curr.Value < x)
13                 {
14                     retcurr.Value = (int)curr.Value;
15                     if (curr.Next != null)
16                     {
17                         retcurr.Next = new LinkedListNode();
18                         retcurr = retcurr.Next;
19                     }
20                 }
21                 curr = curr.Next;
22             }
23 
24             curr = head;
25 
26             while (curr != null)
27             {
28                 if ((int)curr.Value >= x)
29                 {
30                     retcurr.Next = new LinkedListNode();
31                     retcurr = retcurr.Next;
32                     retcurr.Value = (int)curr.Value;
33                 }
34                 curr = curr.Next;
35             }
36 
37             return ret;
38         }

代码分析:

　　O(n)，新建一个linkedlistnode，扫两遍，第一遍把小于x的复制并append到新建的node里面，第二遍，把大于等于x的复制的append。

　　好像有点过于简单。

　　如果要求in place呢，就是空间复杂度要constant。

 1         public static LinkedListNode PartitionList2(LinkedListNode head, int x)
 2         {
 3             if (head == null)
 4                 return null;
 5 
 6             LinkedListNode fakehead = new LinkedListNode();
 7             fakehead.Next = head;
 8 
 9             LinkedListNode curr = fakehead;
10 
11             while (curr.Next != null)
12             {
13                 if ((int)curr.Next.Value < x)
14                 {
15                     curr = curr.Next;
16                 }
17                 //if curr.Next.Value >= x
18                 else
19                 {   
20                     //if curr.Next is the last one, return fakehead.Next
21                     if (curr.Next.Next == null)
22                         return fakehead.Next;
23 
24                     LinkedListNode next = curr.Next;
25                     LinkedListNode prev = curr.Next;
26                     LinkedListNode target = prev.Next;
27 
28                     //find the next node that value < x
29                     while ((int)target.Value >= x)
30                     {
31                         if (target.Next != null)
32                         {
33                             target = target.Next;
34                             prev = prev.Next;
35                         }
36                         else
37                             return fakehead.Next;
38                     }
39 
40                     //swap the nodes (curr.Next and target)
41                     curr.Next = target;
42                     prev.Next = target.Next;
43                     target.Next = next;
44 
45                     curr = curr.Next;
46                 }
47             }
48 
49             return fakehead.Next;
50         }

代码分析：

　　In place的做法。 但是时间复杂度 worse case O(n2)。 看题目要求选择哪个答案吧。

　　代码中建了一个fakehead，然后设fakehead.Next = head，使下面的算法适用于所有node， 包括 head。