題目來(lái)源：
耪遛保客網(wǎng)--程序員面試金典
題目描述
編寫代碼算芯，以給定值x為基準(zhǔn)將鏈表分割成兩部分善已，所有小于x的結(jié)點(diǎn)排在大于或等于x的結(jié)點(diǎn)之前
給定一個(gè)鏈表的頭指針 ListNode* pHead，請(qǐng)返回重新排列后的鏈表的頭指針驱证。注意：分割以后保持原來(lái)的數(shù)據(jù)順序不變躏仇。
解題思路
- 將小于x的值存放于node1鏈表中恋脚，將大于x的值存放于node2鏈表中
- 將node1和node2鏈表進(jìn)行拼接
代碼
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;
}
}
}
