分隔链表
题目描述
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。原题链接
示例
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
解题思路
创建两个头节点，分别表示小于x的链表和大于x的链表，训练遍历原始链表后将其添加到新建的两个链表中，参考代码如下所示：
ListNode* partition(ListNode* head, int x) { ListNode* temp=new ListNode(0); ListNode* low=temp; ListNode* _temp=new ListNode(0); ListNode* big=_temp; ListNode* cur=head; while(cur!=nullptr){ if(cur->val<x){ low->next=cur; low=low->next; } else{ big->next=cur; big=big->next; } cur=cur->next; } // 添加尾节点 big->next=nullptr; low->next=_temp->next; return temp->next; }
算法效果
