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

一、题目

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

二、思路解析

首先，让我们列出我们需要做的事情：

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

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;}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;}
}

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