划分链表
更多算法题解，请关注公众号【程序员学长】
问题形容
LeetCode 面试题 02.04. 宰割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都呈现在 大于或等于 x 的节点之前。并且两个局部之内的节点之间与原来的链表要放弃绝对程序不变。
示例：
输出：head = [1,4,3,2,5,2], x = 3
输入：[1,2,2,4,3,5]
剖析问题
简略来说，咱们只须要保护两个链表small和large即可，使得small链表按顺序存储所有小于x的节点，large链表按顺序存储所有大于等于x的节点。当咱们遍历完链表之后，只须要将small链表的尾节点指向large链表的头结点即可实现宰割链表的操作。
首先，咱们创立两个节点smallHead和largeHead别离为两个链表的哑结点，这是为了不便的解决头结点为空的边界条件，同时smallTail和largeTail别离指向两个链表的开端节点。开始时，smallHead=smallTail，largeHead=largeTail，而后从前往后遍历链表head，判断以后节点的值是否小于x，如果小于x，就将smallTail的next指针指向该节点，否则将largeTail的next指针指向该节点。
遍历完结后，咱们将largeTail的next指针置为空，这是因为以后节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x的节点，咱们须要切断这个援用。而后将smallTail的next指针指向largeHead的next指针指向的节点，来将两个链表合并起来，最初返回smallHead.next即可。
上面咱们来看一下代码实现。
class Solution(object): def partition(self, head, x): #创立两个哑结点 smallHead = smallTail = ListNode(0) largeHead = largeTail = ListNode(0) #遍历链表 while head: #如果head.val<x,将以后节点插入small中，否则插入large中 if head.val < x: smallTail.next=head smallTail=smallTail.next else: largeTail.next=head largeTail=largeTail.next head=head.next largeTail.next=None #合并两个链表 smallTail.next=largeHead.next return smallHead.next该算法的工夫复杂度是O(n)，空间复杂度是O(1)。