TechNomads

题目描述：

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

 

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

解法：

只需要遍历链表的所有节点，小于x的放到一个小的链表中，大于等于x的放到一个大的链表中，最后再把这两个链表串起来即可。

代码

 public ListNode partition(ListNode head, int x) {
        //小链表的头
        ListNode smallHead = new ListNode(0);
        //大链表的头
        ListNode bigHead = new ListNode(0);
        //小链表的尾
        ListNode smallTail = smallHead;
        //大链表的尾
        ListNode bigTail = bigHead;
        //遍历head链表
        while (head != null) {
            if (head.val < x) {
                //如果当前节点的值小于x，则把当前节点挂到小链表的后面
                smallTail = smallTail.next = head;
            } else {//否则挂到大链表的后面
                bigTail = bigTail.next = head;
            }

            //继续循环下一个结点
            head = head.next;
        }
        //最后再把大小链表拼接在一块即可。
        smallTail.next = bigHead.next;
        bigTail.next = null;
        return smallHead.next;
    }

这也是一样的写法

public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(0);
        ListNode bigHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;

        while(head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = smallTail.next;
        
            } else {
                bigTail.next = head;
                bigTail = bigTail.next;
        
            }

            head = head.next;
        }
        smallTail.next = bigHead.next;
        bigTail.next = null;
        return smallHead.next;
    }