86. Partition List

# 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
        : duplicate?
        """
        # find the latest node in the left less than x
        # trick
        # 8:10
        # nums = []
        # while head:
        #     nums.append(head.val)
        #     head = head.next
        # pre_node = ListNode(None)
        # p = pre_node
        # for n in nums:
        #     if n < x:
        #         p.next = ListNode(n)
        #         p = p.next
        # for n in nums:
        #     if n >= x:
        #         p.next = ListNode(n)
        #         p = p.next
        # return pre_node.next
        # 8:27

        # 8:28
        pre_head = None
        pre_end = None
        nex_head = None
        nex_end = None

        while head:
            if head.val < x:
                if pre_head is None:
                    pre_head = head
                    pre_end = head
                else:
                    pre_end.next = head
                    pre_end = pre_end.next
            else: # head.val >= x
                if nex_head is None:
                    nex_head = head
                    nex_end = head
                else:
                    nex_end.next = head
                    nex_end = nex_end.next
            head = head.next

        '''
        !!!!
        nex_end.next = None
        '''
        if nex_end:
            nex_end.next = None
        if pre_head is None:
            return nex_head
        else:
            pre_end.next = nex_head
            return pre_head
        # 8:48

疏忽的点

1. nex_end 是不是为空
2. 重大失误：nex_end 如果存在，那么在程序结尾的时候，一定要把它的 next 置为空。否则就会死循环。