现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
null
cur
指向头节点,即链表的头节点
bs
和be
,分别指向小于x
链表的头节点和尾节点
as
和ae
,分别指向大于等于x
链表的头节点和尾节点
val
值小于x
x
的链表中是否为空,如果为空则bs
和be
都指向当前节点
be
的next
指向当前节点,be
指向be
的next
val
值大于等于x
x
的链表中是否为空,如果为空则as
和ae
都指向当前节点
ae
的next
指向当前节点,ae
指向ae
的next
cur
指向cur
的next
x
的链表为空,则返回as
be
的next
指向as
as
不为空,则将as
的next
值为空(原链表的最后一个节点的值小于x
)
bs
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if (pHead == null) {
return null;
}
// write code here
// 定义cur 指向头结点
ListNode cur = pHead;
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
while (cur != null) {
if (cur.val < x) {
if (bs == null) { // 判断是不是第一个元素
bs = cur;
be = cur;
} else {
be.next = cur;
be = be.next;
}
} else {
if (as == null) {
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
if (be == null) {
return as;
}
be.next = as;
if (as != null) {
ae.next = null;
}
return bs;
}
}
运行结果: