[Leetcode][python]Partition List/分隔链表

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)

        # small_prev和large_prev往后遍历增加，small_dummy和large_dummy则负责最后作为返回头结点
        small_prev = small_dummy
        large_prev = large_dummy
        while dummy.next:  # head第一个节点
            curr = dummy.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            dummy = dummy.next

        large_prev.next = None  # 最后指针置为none
        small_prev.next = large_dummy.next  # large_dummy对应的是大链表的第一个数
        return small_dummy.next  # 返回的是small_dummy