【LeetCode-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):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        # 判断为空或单节点
        if not head:
            return None
        if not head.next:
            return head
        
        # 新建头结点
        res=ListNode(-1)
        res.next=head
        # 双指针，一个遍历结点，一个指向需要插入小于x节点的位置
        pre, cur=res,res

        while cur.next:
            if cur.next.val<x:
                temp_node=ListNode(cur.next.val)
                cur.next=cur.next.next
                temp=pre.next
                pre.next=temp_node
                temp_node.next=temp
                if cur==pre:
                    cur=cur.next
                pre=pre.next
            else:
                cur=cur.next
            
        return res.next