链表分隔。
题目
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
题解
- 双指针法，创建两个带头结点（哑结点）的指针before_x和after_x
- 遍历链表
- 将小于x的值添加到链表before_x中
- 大于等于x的值添加到链表after_x中
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def createLink_rearinsert(lista):
head = ListNode(-1)
rear = head
for i in lista:
new_node=ListNode(i)
rear.next=new_node
rear=new_node
return head.next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
before_x = ListNode(-1)
after_x=ListNode(-1)
b=before_x
a=after_x
while head!=None:
if head.val<x:
b.next=head
b=head
head=head.next
b.next=None
elif head!=None:
a.next=head
a=head
head=head.next
a.next=None
b.next=after_x.next
return before_x.next
if __name__=="__main__":
a=[1,4,3,2,5,2]
x=3
new_a=createLink_rearinsert(a)
a1 = Solution()
p=a1.partition(new_a,x)
list1=[]
while(p!=None):
list1.append(p.val)
p=p.next
print(list1)
|
[1, 2, 2, 4, 3, 5]
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def createLink_rearinsert(lista):
head = ListNode(-1)
rear = head
for i in lista:
new_node=ListNode(i)
rear.next=new_node
rear=new_node
return head.next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
before_x = ListNode(-1)
after_x=ListNode(-1)
b=before_x
a=after_x
while head:
if head.val<x:
b.next=head
b=b.next
else:
a.next=head
a=a.next
head=head.next
a.next = None
b.next=after_x.next
return before_x.next
if __name__=="__main__":
a=[1,4,3,2,5,2]
x=3
new_a=createLink_rearinsert(a)
a1 = Solution()
p=a1.partition(new_a,x)
list1=[]
while(p!=None):
list1.append(p.val)
p=p.next
print(list1)
|
[1, 2, 2, 4, 3, 5]
