算法题--单向链表分区

image.png

0. 链接

题目链接

1. 题目

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

2. 思路1：左右两个指针记录两个分区

3. 代码

# coding:utf8


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        left_head = left_cur = ListNode(0)
        right_head = right_cur = ListNode(0)
        cur = head
        while cur is not None:
            if cur.val < x:
                left_cur.next = cur
                left_cur = left_cur.next
            else:
                right_cur.next = cur
                right_cur = right_cur.next
            cur = cur.next

        right_cur.next = None
        left_cur.next = right_head.next

        return left_head.next


def array_to_linked_list(array):
    head = node = ListNode(-1)
    for each in array:
        node.next = ListNode(each)
        node = node.next
    return head.next


def linked_list_to_array(head):
    array = list()
    node = head
    while node is not None:
        array.append(node)
        node = node.next
    return array


def print_linked_list(head):
    print('->'.join([str(x.val) for x in linked_list_to_array(head)]))


def my_test(solution, array, x):
    print('input:')
    print_linked_list(array_to_linked_list(array))
    print('output:')
    print_linked_list(solution.partition(array_to_linked_list(array), x))
    print('=' * 50)


solution = Solution()
my_test(solution, [1, 4, 3, 2, 5, 2], 3)
my_test(solution, [], 0)
my_test(solution, [1, 1], 2)

输出结果

input:
1->4->3->2->5->2
output:
1->2->2->4->3->5
==================================================
input:

output:

==================================================
input:
1->1
output:
1->1
==================================================

4. 结果

image.png