给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
@Data public static class ListNode { private int val; private ListNode next; public ListNode(int val) { this.val = val; } }
解法1:
public static ListNode partition(ListNode head, int x) { /*定义一个哑节点*/ ListNode dumb = new ListNode(0); /*哑节点的下一个节点指向头节点*/ dumb.next = head; /*定义第一个 >=x节点的前一个节点*/ ListNode slow = null; /*定义第一个 >=x节点的后一个节点*/ ListNode fast = null; /*定义一个前置节点*/ ListNode pre = dumb; while (head != null) { /*如果出现>=x的节点记录下来*/ if (head.val >= x) { slow = pre; fast = pre.next.next; /*pre指向第一个 >=x节点*/ pre = pre.next; break; } pre = head; head = head.next; } /*以fast节点为起点,遍历后面的节点,如果节点值<x,则把这个节点拼接到slow节点的后面*/ while (fast != null) { if (fast.val < x) { pre.next = fast.next; fast.next = slow.next; slow.next = fast; slow = slow.next; } pre = fast; fast = fast.next; } return dumb.next; }
解法2:
public static ListNode partition1(ListNode head,int x){ /*定义小于x的链表哑节点*/ ListNode beforeHead=new ListNode(0); /*定义一个引用指向beforeHead*/ ListNode before=beforeHead; /*定义大于等于x的链表哑节点*/ ListNode afterHead=new ListNode(0); /*定义一个引用指向afterHead*/ ListNode after=afterHead; while (head!=null){ /*如果值大于等于x放在afterHead后面*/ if(head.val>=x){ afterHead.next=head; afterHead=afterHead.next; }else{ /*值小于x的放在beforeHead后面*/ beforeHead.next=head; beforeHead=beforeHead.next; } head=head.next; } /*尾节点的next置为null*/ afterHead.next=null; /*beforeHead的下一个节点指向after的下一个节点,拼接2个链表*/ beforeHead.next=after.next; /*返回第一个链表的下一个节点*/ return before.next; }