题解 | #链表分割#
链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
已知题目要求将小于 x 的值与其他值分开并且前后顺序不能发生改变,那么我们可以创建一个栈,将所有小于 x 的值存放在栈中,然后将栈中的元素一一取出,并采用头插法重新插入链表中.
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 val) {
if(pHead == null) return null;
Stack<Integer> stack = new Stack<>();
ListNode cur = pHead;
ListNode prev = null;
while(cur!=null) {
if(cur.val < val) {
stack.add(cur.val);
if(cur == pHead) {
pHead = pHead.next;
cur = pHead;
}else {
cur = cur.next;
prev.next = cur;
}
}else {
prev = cur;
cur = cur.next;
}
}
while(!stack.isEmpty()) {
ListNode newNode = new ListNode(stack.pop());
newNode.next = pHead;
pHead = newNode;
}
return pHead;
}
}
查看8道真题和解析
投递百度等公司10个岗位 >