面试题 02.04. 分割链表
解题思路
1.分析题意，不需要 保留 每个分区中各节点的初始相对位置，所以简化题目，可以把小于x的放置与左边，大于等于x的放置与右边
2.Java数据结构中，arraylist是基于数组实现的，只能有序添加；linkedlist可以实现无序添加
3.将链表进行遍历，添加到linkedlist中
4.遍历linkedlist，进行result链表
解题遇到的问题
无
后续需要总结学习的知识点
1.借助了LinkedList的特性，如果不使用LinkedList，是否还有其他解法？
2.两次遍历，耗时较大，是否可以优化？
##解法1
class Solution {
public ListNode partition(ListNode head, int x) {
LinkedList<Integer> list = new LinkedList<Integer>();
ListNode t = head;
while (t != null) {
if (t.val >= x) {
list.add(t.val);
} else {
list.addFirst(t.val);
}
t = t.next;
}
int i = 0;
ListNode result = head;
while (head != null) {
head.val = list.get(i);
head = head.next;
i++;
}
return result;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}
