美文网首页
链表的划分

链表的划分

作者: 春天还没到 | 来源:发表于2017-12-07 16:29 被阅读0次

声明: 本总结仅为个人学习总结,以防止遗忘而作,不得转载和商用。
题目:给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的相对顺序。
样例:
给定链表 1->4->3->2->5->2->null,并且 x=3,返回 1->2->2->4->3->5->null
分析:
分别申请两个指针p1和p2,小于x的添加到p1中,大于等于x的添加到p2中;最后,将p2链接到p1的末端即可
时间复杂度O(N),空间复杂度O(1)
Java版本的实现:

public static void partition(Node pHead, int pivotKey){
        //两个链表的头指针
        Node pLeftHead = new Node(0);
        Node pRightHead = new Node(0);
        //两个链表的当前最后一个元素
        Node left = pLeftHead;
        Node right = pRightHead;
        Node p = pHead.next;
        while (p != null) {
            if (p.value < pivotKey) {
                left.next = p;
                left = p;
            }else {
                right.next = p;
                right = p;
            }
            p = p.next;
        }
        //将right链接到left尾部
        left.next = pRightHead.next;
        right.next = null;
        //将整理好的链表赋值给当前链表头部
        pHead.next = pLeftHead.next;
    }

测试代码:

        int datas[] = {1,4,3,2,5,2};
        Node pH = new Node(0);
        for(int i = datas.length-1;i>=0;i--){
            Node pNode = new Node(datas[i]);
            pNode.next = pH.next;
            pH.next = pNode;
        }
        printLinkedList(pH);
        partition(pH, 3);
        printLinkedList(pH);

结果:
Linked List: 0->1->4->3->2->5->2->
Linked List: 0->1->2->2->4->3->5->

相关文章

  • 链表划分

    题目地址两个注意点1、dummy node2、more.next = None 记得较大的链表的next值为non...

  • 链表划分

    LeetCode 86.Partition List已知链表头节点指针head与数值X,将所有小于x的节点放在大于...

  • 链表划分

    描述给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。 你应该保留两部分内链表节点原有...

  • 链表的划分

    声明: 本总结仅为个人学习总结,以防止遗忘而作,不得转载和商用。题目:给定一个单链表和数值x,划分链表使得所有小于...

  • 96. 链表划分

    给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的相对...

  • OJ lintcode 链表划分

    给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的相对...

  • 96.链表划分

    描述给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的...

  • LintCode 练习代码

    35.翻转链表 165. 合并两个排序链表 96. 链表划分 166. 链表倒数第n个节点 java语言一次循环定...

  • [LeetCode]86. Partition List

    86. Partition List 题意: 给出一个链表和一个数字M, 将这个链表划分为两个链表.第一个链表是小...

  • 单向链表划分区域

    题目: 思路1: 把单向链表转化为结点数组,利用数组的partition过程(快排中),划分成要求的大于区小于区等...

网友评论

      本文标题:链表的划分

      本文链接:https://www.haomeiwen.com/subject/vtfjixtx.html