小黑leetcode之旅:86. 分隔链表

小黑做法：硬做

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 添加辅助结点
        head = ListNode(next = head)
        # 前指针pre_link
        pre_link = head
        # 后指针link
        link = head.next
        # 辅助数组
        temp_arr = []
        # 两个指针不停地移动
        while link:
            # 出现大于等于x的数字时停止
            if link.val >= x:
                break
            link = link.next
            pre_link = pre_link.next
        # 前指针a_link指向第一个大于等于x的数
        a_link= pre_link.next
        # 如果没有大于等于x的数字则直接返回
        if not link:
            return head.next
        # 后指针b_link
        b_link = link.next
        arr = []
        while b_link:
            # 小于x的数字放入arr,并在链表中删除
            if b_link.val < x:
                arr.append(b_link)
                a_link.next = b_link.next
            else:
                a_link = a_link.next
            b_link = b_link.next
        # arr中元素插入到pre_link后
        link_arr = pre_link
        for node in arr:
            link_arr.next = node
            link_arr = link_arr.next
        link_arr.next = link
        return head.next
            
            
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

模拟法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 小结点
        small_head = ListNode()
        small = small_head
        # 大结点
        big_head = ListNode()
        big = big_head
        while head:
            if head.val  x:
                small.next = head
                small = small.next
            else:
                big.next = head
                big = big.next
            head = head.next
        small.next = big_head.next
        big.next = None
        return small_head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

小黑生活

下午要去朝阳公园跑步，喝喜茶!!!