现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
我们可以假设x为36,则小于36都排在前边,>36排在后面。
则大致可以分为两个区域来存储数据:区域一存储小于36,区域二存储大于36.
同时,不能改变数据顺序,那这里就要用到尾插法。将数据逐个插进去。
这里我们可以看到,当所有数据插入后,中间部分是要连接起来的,我们不妨创建4个节点bs(表头),be(表尾),as(表头),ae(表尾),最后可以通过be和as将数据连接起来。
具体步骤:
1.创建4个节点,并都置为空,同时创建一个cur节点,作为链表的头。
ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;
2.头节点不为空,从头节点开始,比较x与cur的值,若<x,若此时bs为空(第一次插入),则将bs和be均置为cur(头/末节点),让cur++,到达下一位置(0x89), 此时再次比较,23<36,1且 bs!=null,此时将尾节点置为第二个元素(0x89):
be.next = cur ; be = be.next ()
若>x:
第一次插入时,as,ae均为0,则将as与be置为cur(对接前边元素),同时cur++,
二次比较时,和上述类似:
ae.next = cur; ae = ae.next;
while(cur !=null){if(cur.val<x){//第一次插入if(bs == null){bs = be = cur;}else{be.next = cur;be = be.next;}}else{if(as ==null){as = ae = cur;}else{ae.next = cur;ae= ae.next;}}cur = cur.next;}
3.结尾收工:bs或as两者之一有可能为空,哪个为空,就返回不为空的那个,两个清况都要写。
其次,在尾插区域二时,最后一个元素的地址可能为空,所以当as!=null时,我们要将ae.next置为空,防止越界。
if(bs == null){return as;}be.next = as;if(as!=null){ae.next = null;}return bs;}