描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if(pHead == null || pHead.next == null){
return pHead;
}
//newHead的指针
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
//pHead的指针
ListNode preCur = pHead;
ListNode cur = preCur.next;
//把小于x的节点放进newHead链表里
//其余结点不动
while(cur != null){
if(cur.val < x){
preCur.next = cur.next;
tmp.next = cur;
tmp = tmp.next;
cur = preCur.next;
}else{
preCur = preCur.next;
cur = preCur.next;
}
}
//判断头节点并拼接链表newHead -> pHead
if(pHead.val < x){
cur = pHead;
pHead = pHead.next;
cur.next = newHead.next;
tmp.next = pHead;
return cur;
}else{
tmp.next = pHead;
return newHead.next;//删除pHead中的头节点
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/hz/140691.html