关于leetcode:完虐算法划分链表

划分链表

更多算法题解，请关注公众号【程序员学长】

问题形容

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)。