86. 分隔链表（java链表）

题目

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

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

示例:

输入: head = 1->4->3->2->5->2, _x_ = 3 输出: 1->2->2->4->3->5

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode partition(ListNode head, int x) { ListNode root1 = new ListNode(0), root2 = new ListNode(0); ListNode r1 = root1, r2 = root2, p = head; while (p != null){ ListNode t = p; p = p.next; if (t.val < x){ r1.next = t; r1 = t; } else { r2.next = t; r2 = t; } } r1.next = root2.next; r2.next = null; return root1.next; } }