一、题目
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
二、思路解析
首先,让我们列出我们需要做的事情:
Sounds simple, right?
Step 1: 选择好用什么结构来存储值小于 x 的元素
这里我采用的是题解区中一位大佬的解法,他是用栈来存储那些待会要头插于链表的、值小于 x 的元素的。
我们首先定义一个栈来存储所有小于x的节点的值。
如果你对栈不熟悉,没关系,想象一下你在吃饭时堆放碗筷的样子,最后放上去的碗筷总是最先被取走,栈就是这样工作的。
Step 2: 遍历链表
遍历过程,如果我们遇到一个值小于x的节点,我们就把它的值压入栈中,并从原链表中删除这个节点。
如何删除节点,只需要把它前面节点的 next 指针指向它的下一个节点即可。
Step 3: 把栈中元素用头插法,插入链表
在我们遍历完链表后,所有小于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 x) {
- // write code here
-
- if(pHead == null){return null;}
-
- Stack<Integer> stack = new Stack<>();
- ListNode cur = pHead;
- ListNode prev = null;
-
- while(cur != null){
- if(cur.val < x){
- 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;
- }
- }
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!