leetcode86. Partition List

layman 发布于2019-08-15 10:45 / 3463人阅读

摘要：当前节点的前一个节点插入位置的前一个节点，以及记录初始位置的节点。当发现一个需要交换的节点时，先获得这个节点，然后将指向节点的后一个节点。最后将两个链表连接。代码相比于第一种更加清晰一些。

题目要求

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

将小于x的值放在前面，大于等于x的值放在后面，移动的过程中不改变数字之间的相对顺序。

思路一：移动节点

该思路需要我们记录3个节点。当前节点的前一个节点currentPrev,插入位置的前一个节点prev，以及记录初始位置的节点start。当发现一个需要交换的节点时，先获得这个节点，然后将currentPrev指向节点的后一个节点。之后将当前的节点插入到prev之后。代码如下：

    public ListNode partition(ListNode head, int x) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode start = new ListNode(0);
        ListNode prev = new ListNode(0);
        ListNode currentPrev = new ListNode(0);
        start.next = prev;
        prev.next = head;
        currentPrev.next = head;
        while(currentPrev.next!=null && currentPrev.next.val
思路二：使用两个链表
我们设置两个头指针当做两个链表，当遇到的数值小于x，则加入第一个链表，否则加入第二个链表。最后将两个链表连接。代码相比于第一种更加清晰一些。
    public ListNode partition2(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode curr = head, first = dummy1, second = dummy2;
        while (curr != null) {
            if (curr.val < x) {
                first.next = curr;
                first = first.next;
            } else {
                second.next = curr;
                second = second.next;
            }
            curr = curr.next;
        }
        first.next = dummy2.next;
        second.next = null;
        return dummy1.next;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

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

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

[LeetCode] 86. Partition List

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 ea...

Yuqi 2019-08-16 13:54 评论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 2019-08-16 13:58 评论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...

崔晓明 2019-08-14 16:26 评论0 收藏0
[Leetcode] Palindrome Partitioning 回文分割

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

leanote 2019-08-14 12:32 评论0 收藏0