将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】给定一个单链表的头节点head,节点
数pivot。实现一个调整链表的函数,将徙衣笈~'i力匀ivot的节点。节点,中间部分都是值等于pivot的节点,右部分都是值大于pivot的节点。
【进阶】在实现原问题功能的基础上增加如下的要求
【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样【要求】时间复杂度请达到0(N),额外空间复杂度请达到0(1)。
思想
- 准备六个结点,分别是小于链表的链首和尾,等于链表的首尾以及大于链表的首尾
- 遍历传入的链表,将每一个元素与目标值做比较,如果小于目标值则尾插入小于链表的链尾,等于则尾插入等于链表的链尾,大于等尾插入大于链表的链尾
- 最后依次将小于链表的链尾,等于链表的链首以及大于链表的链首相连(如果三个链表都不为空)。当其中有一个或两个链表为空,则不连接该链表
性能
时间复杂度为O(n)
空间复杂度为O(1)
性能稳定
代码
package ListNode;
import Pojo.ListNode;
public class ListNode_partition {
public static void main(String[] args) {
int arr[] = {10, 5, 6, 8, 8, 6, 5, 10};
Huiwen my = new Huiwen();
ListNode node = null;
ListNode firstNode = null;
// 采用头插法建立单链表
for (int i =0; i < arr.length; i++)
{
ListNode listNode = new ListNode(arr[i]);
if (node == null)
{
node = listNode;
firstNode = node;
}
else
{
node.next = listNode;
node = listNode;
}
System.out.print(node.data + ", ");
}
System.out.println();
ListNode listNode = listPartition(firstNode, 8);
//System.out.println(listNode == null);
while (listNode != null)
{
System.out.print(listNode.data + ", ");
listNode = listNode.next;
}
}
public static ListNode listPartition(ListNode listNode, int pivot)
{
ListNode sH = null;
ListNode sT = null;
ListNode eH = null;
ListNode eT = null;
ListNode gH = null;
ListNode gT = null;
while (listNode != null)
{
ListNode next = listNode.next;
listNode.next = null;// 不可少,这是为了使其成为一个独立的结点,不指向其他的结点,以方便加入其他链表
// 如果当前结点的值小于目标值,则加入 小于链表的链尾
if (listNode.data < pivot)
{
// 第一次加入时,链表为空,头尾都指向第一个结点
if (sH == null)
{
sH = listNode;
sT = listNode;
}
else
{
sT.next = listNode;
sT = listNode;
}
}
// 如果当前结点的值等于目标值,则加入 等于 链表的链尾
else if (listNode.data == pivot)
{
if (eH == null)
{
eH = listNode;
eT = listNode;
}
else
{
eT.next = listNode;
eT = listNode;
}
}
// 如果当前结点的值大于目标值,则加入 大于链表的链尾
else
{
if (gH == null)
{
gH = listNode;
gT = listNode;
}
else
{
gT.next = listNode;
gT = listNode;
}
}
listNode = next;
}
// 因为序列的数值分布状况不同,可能遍历下来,只存在大于链表,也可能存在小于链表和大于链表,因此需要做出相应的判断
// small and equal reconnect
// 如果小于区域存在,将小于区域的尾结点的next指向等于区域的头部,
if (sT != null)
{
sT.next = eH;
eT = eH == null ? sT : eT; // 决定由哪个区域的链尾去链接大于区域的头
}
// 不管上面这个if有没有执行,eT都需要被判断
if (eT != null) // 如果小于区域不是都没有
eT.next = gH;
// 如果小于区域存在,返回小于区域的链首,不存在则返回等于区域的链首,还不存在则返回大于区域的链首部
return sH != null ? sH : (eH != null ? eH : gH);
}
}