86. 分隔链表

题目描述

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

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

示例:

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

我的解法——两个指针append后合并（AC）

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

class Solution(object):
    def append(self, now, head, tail):
        temp = now.next
        now.next = None
        if(not head):
            head = now
            tail = now
        else:
            tail.next = now
            tail = tail.next
        return head, tail, temp
    
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if(not head):
            return None
        less_head = None
        less_tail = None
        more_head = None
        more_tail = None
        now = head
        
        while(now):
            if(now.val < x):
                less_head, less_tail, now = self.append(now, less_head, less_tail)
            else:
                more_head, more_tail, now = self.append(now, more_head, more_tail)
        
        if(not less_head):
            return more_head
        else:
            less_tail.next = more_head
        return less_head