【LeetCode每天一题】Partition List(分区链表)

80 阅读 0 评论 53 点赞

我是靠谱客的博主威武火龙果，最近开发中收集的这篇文章主要介绍【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

思路

　　这道题最简单的思路就是我们可以将链表中的数据全部都添加进数组中，然后对数组中的元素按照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