python实现leetcode之86. 分隔链表

解题思路

first_half尾插法保存小于x的元素
second_half尾插法保存大于等于x的元素
最后第一部分的尾部接第二部分的头部
保险起见，将第二部分的尾部设置为None
最后返回first_half头

亮点，使用ListNode(0)哨兵优化代码行

86. 分隔链表

代码

# 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):
        first_half = first_tail = ListNode(0)
        second_half = second_tail = ListNode(0)
        while head:
            tmp = head.next
            if head.val < x:  # add to first_half
                first_tail.next = head
                first_tail = head
            else:  # add to second half
                second_tail.next = head
                second_tail = head
            head = tmp
        
        first_tail.next = second_half.next
        second_tail.next = None
        return first_half.next