划分链表

问题描述

面试题 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即可。

更多题解，关注公众号【程序员学长】，100多道高频题送个你

下面我们来看一下代码实现。

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