资讯专栏INFORMATION COLUMN

[LeetCode] 86. Partition List

Yuqi / 2726人阅读

Problem

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

Solution
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode small = dummy1, large = dummy2;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        small.next = dummy2.next;
        large.next = null;
        return dummy1.next;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/72529.html

相关文章

  • leetcode86. Partition List

    摘要:当前节点的前一个节点插入位置的前一个节点,以及记录初始位置的节点。当发现一个需要交换的节点时,先获得这个节点,然后将指向节点的后一个节点。最后将两个链表连接。代码相比于第一种更加清晰一些。 题目要求 Given a linked list and a value x, partition it such that all nodes less than x come before no...

    layman 评论0 收藏0
  • [LeetCode] 763. Partition Labels

    Problem A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers represe...

    iliyaku 评论0 收藏0
  • [LintCode/LeetCode] Partition List

    摘要:新建两个链表,分别存和的结点。令头结点分别叫作和,对应的指针分别叫作和。然后遍历,当小于的时候放入,否则放入。最后,让较小值链表尾结点指向较大值链表头结点,再让较大值链表尾结点指向。 Problem Given a linked list and a value x, partition it such that all nodes less than x come before no...

    崔晓明 评论0 收藏0
  • [Leetcode] Palindrome Partitioning 回文分割

    摘要:深度优先搜素复杂度时间空间思路因为我们要返回所有可能的分割组合,我们必须要检查所有的可能性,一般来说这就要使用,由于要返回路径,仍然是典型的做法递归时加入一个临时列表,先加入元素,搜索完再去掉该元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

    leanote 评论0 收藏0

发表评论

0条评论

Yuqi

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<