0086. Partition List

发布于：2020年10月20日

86. Partition List Medium

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:

1 2	Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5

思路：

思路一：大小链表

原链表：1 -> 4 -> 3 -> 2 -> 5 -> 2

大链表：4 -> 3 -> 5
小链表：1 -> 2 -> 2

合并链表：1 -> 2 -> 2 -> 4 -> 3 -> 5

代码：

    public ListNode partition(ListNode head, int x) {
//        Input: head = 1->4->3->2->5->2, x = 3
//        Output: 1->2->2->4->3->5
        // 小链表
        ListNode min = new ListNode(-1);
        ListNode l  = min;

        // 大链表
        ListNode max = new ListNode(-1);
        ListNode h = max;

        while (head != null) {
            if (head.val < x) {
                l.next = head;
                l = l.next;
            }
            else {
                h.next = head;
                h = h.next;
            }
            head = head.next;
        }
        h.next = null;
        l.next = max.next;
        return min.next;
    }

时间复杂度：O(n)

空间复杂度：O()

更新于：2020年10月20日

Leetcode

LinkedList

0092. Reverse Linked List II

92. Reverse Linked List II Medium难度中等551 Reverse a linked list from position m to n. Do it in one...

0083. Remove Duplicates from Sorted List

83. Remove Duplicates from Sorted List EasyGiven a sorted linked list, delete all duplicates such...