Leetcode034--将单链表进行分区

一、原题

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. 

一、中文

给定一个单链表和一个值x，将链表分成小于等于x的部分和大于x的部分。同时保持链表原来的相对顺序

三、举例

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

四、思路

  创建两个链表，编译单链表，将链表中比较小的元素放到左边的链表中，比较大的放入到右边的链表中

最后将两个链表进行合并就可以了。

五、程序

  package code; public class LeetCode47{ public static void main(String args[]){ ListNode list1 = new ListNode(1); ListNode list2 = new ListNode(4); ListNode list3 = new ListNode(2); ListNode list4 = new ListNode(2); ListNode list5 = new ListNode(5); list1.next = list2; list2.next = list3; list3.next = list4; list4.next = list5; ListNode list = partition(list1, 3); while(list != null){ System.out.print(list.val+" "); list = list.next; } } //将链表以x为依据分割开来 public static ListNode partition(ListNode head, int x) { ListNode left = new ListNode(); ListNode tmpLeft = left; ListNode right = new ListNode(); ListNode tmpRight = right; if(head == null || head.next == null){ return head; } while(head != null){ if(head.val <= x){ ListNode tmp = new ListNode(); tmp.val = head.val; left.next = tmp; left = left.next; } if(head.val > x){ ListNode tmp = new ListNode(); tmp.val = head.val; right.next = tmp; right = right.next; } head = head.next; } //将左右两个链表进行连接 left.next = tmpRight.next; return tmpLeft.next; } } ------------------------------------------output------------------------------------------- 1 2 2 4 5