寒光博客

[LeetCode]面试题 02.04 分割链表 and 86.分割链表
题目 编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,...
扫描右侧二维码阅读全文
15
2020/07

[LeetCode]面试题 02.04 分割链表 and 86.分割链表

题目

编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。
分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。
https://leetcode-cn.com/problems/partition-list-lcci/
示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

Related Topics 链表 双指针
👍 21 👎 0

分析及反思

双指针法,思路类似于“荷兰国旗🇳🇱”的颜色排序题目.
p指针左边必定是小于x的节点,q指针遍历链表,遇到val<x时,交换p,q的val,并且p=p.next

其中不需要保持原有的顺序86题需要。所以有所异同。
https://leetcode-cn.com/problems/partition-list/

代码

该题 不需要保持原有顺序

info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.3 MB,击败了100.00% 的Java用户

class Solution {

    public ListNode partition(ListNode head, int x) {
        ListNode p, q;
        p = q = head;
        while (q != null) {
            if (q.val < x) {//肯定是大于等于的交换
                int t = q.val;
                q.val = p.val;
                p.val = t;
                p = p.next;
            }
            q = q.next;
        }
        return head;
    }
}

86题 保持后者的大小相对顺序

11:06 info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.2 MB,击败了5.55% 的Java用户

class Solution {
    public ListNode partition(ListNode head, int x) {
        //维护两条链表,利用尾插法保证相对顺序不变
        ListNode min = new ListNode(-1);
        ListNode max = new ListNode(-1);
        ListNode p = head, p1 = min, p2 = max;//mark 链表的头。

        while (p != null) {
            if (p.val < x) {
                min.next = p;
                min = min.next;
            } else {
                max.next = p;
                max = max.next;
            }
            p = p.next;
        }
        min.next = p2.next;//小的尾巴指向大的头部 尾插法
        max.next = null;///对于非空表,将尾结点指针域置空 否则 Error - Found cycle in the ListNode
        return p1.next;
    }
}
本文作者:Author:     文章标题:[LeetCode]面试题 02.04 分割链表 and 86.分割链表
本文地址:http://dxoca.cn/Algorithm/372.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 15th, 2020 at 11:26 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment