面试题 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;
        }
    }
}