佛山网站设计专业,浙江网站建设哪里有,网站表单提交,阿里云上如何用iis做网站一、题目 现有一链表的头指针 ListNode* pHead#xff0c;给一定值x#xff0c;编写一段代码将所有小于x的结点排在其余结点之前#xff0c;且不能改变原来的数据顺序#xff0c;返回重新排列后的链表的头指针。 二、思路解析 首先#xff0c;让我们列出我们需要做的事情给一定值x编写一段代码将所有小于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 hereif(pHead null){return null;}StackInteger 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;}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
