题目来源：

牛客网--程序员面试金典

题目描述

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

解题思路

1. 将小于x的值存放于node1链表中，将大于x的值存放于node2链表中
2. 将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;
        }
        
    }
}