【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:

复制代码　　Input: head = 1->4->3->2->5->2, x = 3 　　Output: 1->2->2->4->3->5思路

1
2
　　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
　　这道题最简单的思路就是我们可以将链表中的数据全部都添加进数组中，然后对数组中的元素按照x进行划分，得到划分之后的数组再组成链表。但是这种办法再应对链表比较长的时候就会存在问题。时间复杂度为O(n)(省略了系数), 空间复杂度为O(n)。另一种解法是我们可以直接该改变指针的方向，原地对链表进行分区。时间复杂度为O(n), 空间复杂度为O(1)。
图示解法

---

复制代码解决代码

1
解决代码

---

复制代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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 or not head.next:
            return head
        
        res = ListNode(0) = one      # 哨兵节点

        while True:
            while one.next and one.next.val < x:   # 便利到下一个节点大于x市停止。
                one = one.next       
            two = one.next                              # two节点从这个one的下一个节点来找到下一个节点小于x的系欸但使停止
            while two.next and two.next.val >= x:
                two = two.next
                
            if not two.next or not one.next:             # 如果两个节点任意一个为空，则表示没找到满足条件的节点。
                return res.next            
            tem = two.next                                #  交换节点的指向为止，注意顺序不能改变，否则会出错。
            two.next  =  tem.next
            tem.next  =  one.next
            one.next  =  tem

复制代码

1