怒刷 LeetCode 100 道 (86)

來自專欄編程人生

題目

Description:

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.

Example:

Input: head = 1->4->3->2->5->2, x = 3Output: 1->2->2->4->3->5

解法

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def partition(self, head, x): """ :type head: ListNode :type x: int :rtype: ListNode """ chain1 = ListNode(0) chain2 = ListNode(0) tmp1 = chain1 tmp2 = chain2 tmp = head while tmp: if tmp.val < x: tmp1.next = tmp tmp1 = tmp1.next else: tmp2.next = tmp tmp2 = tmp2.next tmp = tmp.next tmp2.next = None tmp1.next = chain2.next return chain1.next

推薦閱讀：