1. 题目描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
2. 思路
- 判断链表是否为空，如果为空返回
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
3. 代码
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; } }
运行结果：
