面试题 02.04. 分割链表

题目链接

题意：⊙▂⊙，就是把小于x的节点放在前面，其他的不管，题目只要小于x的节点在左边就行。（但是我不是这么写的TAT，我写的小于等于x的节点放在左边，其他的放在右边）。

    /**
     * 
     * 记录第一种自己想出的比较low的写法。
     * 额外创建两个链表，一个链表用来存储小于x的节点，
     *                 一个链表用来存储大于或者等于x的节点
     */
    public ListNode partition(ListNode head, int x) {
        //小于x
        ListNode listNode1 = new ListNode( -1 );
        ListNode head1 = listNode1;

        //大于等于x
        ListNode listNode2 = new ListNode( -1 );
        ListNode head2 = listNode2;

        //只要当前不等于空，就一直循环
        while(  null != head ){
            if( head.val < x ){
                listNode1.next = new ListNode( head.val );
                listNode1 = listNode1.next;
            }
            else{
                listNode2.next = new ListNode( head.val );
                listNode2 = listNode2.next;
            }
            head = head.next;
        }
        //这里要注意额外创建的小于x的链表可能为“空”
        if( head1.next == null ){
            return head2.next;
        }
        //这里要注意额外创建的大于等于x的链表可能为“空”
        else if( head2.next == null ){
            return head1.next;
        }
        //如果额外创建的两个链表都不为空
        else{
            head1 = head1.next;
            head2 = head2.next;
            listNode1.next = head2;
            return head1;
        }
    }

参考优质代码，自己又写了一遍。

       public ListNode partition(ListNode head, int x) {
        //小于x
        ListNode leftHead = new ListNode( -1 );
        ListNode leftCurrent = leftHead;

        //大于等于x
        ListNode rightHead = new ListNode( -1 );
        ListNode rightCurrent = rightHead;

        //只要当前不等于空，就一直循环
        while(  null != head ){
            if( head.val < x ){
                leftCurrent.next = new ListNode( head.val );
                leftCurrent = leftCurrent.next;
            }
            else{
                rightCurrent.next = new ListNode( head.val );
                rightCurrent = rightCurrent.next;
            }
            head = head.next;
        }
        leftCurrent.next = rightHead.next;
        return leftHead.next;
    }