【题目描述】

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

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

示例:

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

【解答】

# 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

                

【代码分析】

1. 新建头节点，res指向head
2. 创建两个指针，一个用于遍历节点（cur），一个用于记录小于x的节点的插入位置(pre)
3. cur，pre先指向res，然后开始遍历
4. 判断cur下一个节点是否小于x，如果小于就插入到pre的位置
5. 注意：如果插入了新的节点，cur==pre，则需要跳转到下一个节点，否则不需要，比如：1-4-3-2      此时pre cur都在1这，2插入到1后面后，需要把cur指向2，即cur=cur.next，但是如果是 1-2-4-3-2-5，此时pre在2，cur在3的话，把后面的2插入到前面2的后面，1-2-2-4-3-5，此时cur在3，它的next已经变成了5，还需要继续判断，因此不需要cur=cur.next
6. 如果cur下一个节点大于x，直接查看下一个节点
7. 最终返回res.next