86. Partition List

题目要求：

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Examples：

Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解题思路：

• 使用两个链表: < target ：插入到less_head链表里；> target ：插入到more_head链表里，最后将两个链表相连接。
• 示意图

代码：

class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))


class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        less_head = ListNode(0)
        more_head = ListNode(0)
        less_ptr = less_head
        more_ptr = more_head

        while head:
            if head.val < x:
                less_ptr.next = head
                less_ptr = head
                head = head.next
                less_ptr.next = None

            else:
                more_ptr.next = head
                more_ptr = head
                head = head.next
                more_ptr.next = None

        less_ptr.next = more_head.next

        return less_head.next


if __name__ == "__main__":
    head, head.next, head.next.next = ListNode(1), ListNode(5), ListNode(3)
    head.next.next.next, head.next.next.next.next = ListNode(3), ListNode(4)
    head.next.next.next.next.next, head.next.next.next.next.next.next = ListNode(4), ListNode(5)

    print(Solution().partition(head, 4))