题目来源：
牛客网--程序员面试金典
题目描述
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。
解题思路
- 将小于x的值存放于node1链表中，将大于x的值存放于node2链表中
- 将node1和node2链表进行拼接
代码
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode current = pHead;
ListNode node1_head = null;
ListNode node1_last = null;
ListNode node2_head = null;
ListNode node2_last = null;
while(current != null){
if(current.val < x){
if(node1_head == null){
node1_head = new ListNode(current.val);
node1_last = node1_head;
}else{
ListNode newNode = new ListNode(current.val);
node1_last.next = newNode;
node1_last = newNode;
}
}else{
if(node2_head == null){
node2_head = new ListNode(current.val);
node2_last = node2_head;
}else{
ListNode newNode = new ListNode(current.val);
node2_last.next = newNode;
node2_last = newNode;
}
}
current = current.next;
}
if(node1_head == null){
return node2_head;
}else{
node1_last.next = node2_head;
return node1_head;
}
}
}
