【LeetCode每天一题】Partition List(分区链表)
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:
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
思路
这道题最简单的思路就是我们可以将链表中的数据全部都添加进数组中，然后对数组中的元素按照x进行划分，得到划分之后的数组再组成链表。但是这种办法再应对链表比较长的时候就会存在问题。时间复杂度为O(n)(省略了系数), 空间复杂度为O(n)。另一种解法是我们可以直接该改变指针的方向，原地对链表进行分区。时间复杂度为O(n), 空间复杂度为O(1)。
图示解法
解决代码
1 # Definition for singly-linked list.
2 # class ListNode(object):
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution(object): 8 def partition(self, head, x): 9 """
10 :type head: ListNode 11 :type x: int 12 :rtype: ListNode 13 """
14 if not head or not head.next: 15 return head 16
17 res = ListNode(0) = one # 哨兵节点 18
19 while True: 20 while one.next and one.next.val < x: # 便利到下一个节点大于x市停止。 21 one = one.next 22 two = one.next # two节点从这个one的下一个节点来找到下一个节点小于x的系欸但使停止 23 while two.next and two.next.val >= x: 24 two = two.next 25
26 if not two.next or not one.next: # 如果两个节点任意一个为空，则表示没找到满足条件的节点。 27 return res.next 28 tem = two.next # 交换节点的指向为止，注意顺序不能改变，否则会出错。 29 two.next = tem.next 30 tem.next = one.next 31 one.next = tem
更多精彩
