这周一道算法题(六十三)

本周题目难度级别'Medium',使用语言'Python'，好久没写链表的题了，顺便也熟悉下Python对链表的操作

题目：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。(eg:head = 1->4->3->2->5->2, x = 3返回新的链表head=1->2,2,4,3,5)

思路：遍历一遍即可，先找到第一个大于x的前一个节点(记为pre节点)，然后把后面比x小的节点都放到pre节点的后面就行了。思路很简单，不过我实现了好久，下面看代码即可：

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

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        # 找到第一个大于等于x的数的前一个节点
        pre = head
        cur = head 
        while cur:
            if cur.val >= x:
                tem = cur
                break
            else:
                pre = cur
            cur = cur.next
        if cur:
            # 继续遍历，如果遇到比x小的数就放到前面去
            cur = cur.next
            while cur:
                if cur.val < x:
                    # 需要交换头节点
                    if pre == head and head.val >= x:
                        tem.next = cur.next
                        cur.next = head
                        head = cur
                        pre = cur
                    else:
                        tem.next = cur.next
                        cur.next = pre.next
                        pre.next = cur
                        pre = pre.next
                        cur = tem
                tem = cur
                cur = cur.next
        return head

效率不错，代码中的两个while可以合并成一个，但一个while的效率比两个while的效率低，所以我就不合并了

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!