86. 分隔链表 [medium]

https://leetcode-cn.com/problems/partition-list/

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

通过次数41,934 | 提交次数71,788

First Try

2020-07-06

使用模拟法一个个处理，发现用双指针实现上浮效果就可以了。 tricky点在于需要提前判断left和pre这两个双指针是否相等，如果相等的话，在链表指针关联情况下，结果会莫名其妙，各种互相关联debug都困难。

另外在head前面放个dummy节点确实给力啊，就可以在遍历过程中把head点也处理了。而且这样还不需要提前考虑head是否为空节点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        # 搞个额外的列表算不算作弊？
        # 算了不搞额外列表，使用模拟法一个个处理，发现用双指针实现上浮效果就可以了
        dummy = ListNode(None)
        dummy.next = head 
        left = pre = dummy 

        while pre.next:
            node = pre.next
            # 没有判断left和pre是否相等的时候，结果混乱得莫名其妙
            if node.val < x and pre != left:
                pre.next = node.next
                b = left.next 
                left.next = node   
                node.next = b
                left = left.next
            elif node.val < x and pre == left:
                pre = node 
                left = pre 
            else:
                pre = node
                
        return dummy.next 

执行用时：24 ms, 在所有 Python 提交中击败了75.63%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了33.33%的用户

86. 分隔链表 [medium]​

First Try​

86. 分隔链表 [medium]

First Try