• 『力扣刷题本』:链表分割


    一、题目

    现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

    二、思路解析

    首先,让我们列出我们需要做的事情:

    1. 遍历整个链表;
    2. 对于值小于x的节点,把它们暂时存储起来,并从原链表中删除「删除是为了等下重新插入的时候,不造成元素重复的情况」;
    3. 最后,我们要把这些节点重新插入到链表的头部。

    Sounds simple, right? 

    Step 1: 选择好用什么结构来存储值小于 x 的元素

    这里我采用的是题解区中一位大佬的解法,他是用栈来存储那些待会要头插于链表的、值小于 x 的元素的。

    我们首先定义一个栈来存储所有小于x的节点的值。

    如果你对栈不熟悉,没关系,想象一下你在吃饭时堆放碗筷的样子,最后放上去的碗筷总是最先被取走,栈就是这样工作的。

    Step 2: 遍历链表

     遍历过程,如果我们遇到一个值小于x的节点,我们就把它的值压入栈中,并从原链表中删除这个节点。

    如何删除节点,只需要把它前面节点的 next 指针指向它的下一个节点即可。

    Step 3: 把栈中元素用头插法,插入链表

    在我们遍历完链表后,所有小于x的节点都已经被保存在了栈中,而由于栈的先进后出特性,我们可以保证最早被删除的节点最后被添加回链表。

    因此,我们从栈顶开始,每次弹出一个节点,然后创建一个新的节点,并将其添加到链表的头部。这样,我们就可以保证节点的原始顺序被保持。

    这就是这道题的完整解题思路啦,下面请看完整代码~

    三、完整代码

    1. import java.util.*;
    2. /*
    3. public class ListNode {
    4. int val;
    5. ListNode next = null;
    6. ListNode(int val) {
    7. this.val = val;
    8. }
    9. }*/
    10. public class Partition {
    11. public ListNode partition(ListNode pHead, int x) {
    12. // write code here
    13. if(pHead == null){return null;}
    14. Stack<Integer> stack = new Stack<>();
    15. ListNode cur = pHead;
    16. ListNode prev = null;
    17. while(cur != null){
    18. if(cur.val < x){
    19. stack.add(cur.val);
    20. if(cur == pHead){
    21. pHead = pHead.next;
    22. cur = pHead;
    23. }else{
    24. cur = cur.next;
    25. prev.next = cur;
    26. }
    27. }else{
    28. prev = cur;
    29. cur = cur.next;
    30. }
    31. }
    32. while(!stack.isEmpty()){
    33. ListNode newNode = new ListNode(stack.pop());
    34. newNode.next = pHead;
    35. pHead = newNode;
    36. }
    37. return pHead;
    38. }
    39. }

    以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!

  • 相关阅读:
    Android 远程调用服务之 AIDL
    FragmentManager is already executing transactions异常
    文献解读|植物对低温胁迫的反应:低温胁迫改变了大白菜的抗氧化代谢能力
    【交通建模】基于模型的自主交通仿真框架附matlab代码
    Avalonia 部署到麒麟信安操作系统
    2022/9/13总结
    测试/开发程序员为什么这么吃香,高薪的“孤独症患者“......
    企业云网盘:如何选择最适合您的解决方案?
    时序预测 | MATLAB实现CNN-LSTM卷积长短期记忆神经网络时间序列预测(风电功率预测)
    精确率、准确率、召回率
  • 原文地址:https://blog.csdn.net/C_Small_Cai/article/details/134489305