T O P

[资源分享]     在链表上实现 Partition 以及荷兰国旗问题

  • By - 楼主

  • 2022-11-24 22:04:17
  • 在链表上实现 Partition 以及荷兰国旗问题

    作者:Grey

    原文地址:

    博客园:在链表上实现 Partition 以及荷兰国旗问题

    CSDN:在链表上实现 Partition 以及荷兰国旗问题

    题目描述

    给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

    你应当 保留 两个分区中每个节点的初始相对位置。

    题目链接见:LeetCode 86. Partition List

    主要思路

    本题可以借鉴数组的 Partition 操作,参考:荷兰国旗问题与快速排序算法

    Partition 操作就是荷兰国旗的一种特殊情况而已。

    我们可以把本题的难度稍微升级一下:如何在链表上实现荷兰国旗问题?

    第一种解法就是将链表先转换成数组,然后在数组上实现荷兰国旗问题,最后将数组还原为链表并返回,该方法的时间复杂度是O(N),空间复杂度是O(N),不是最优解。

    第二种解法是用有限几个变量来实现,在同样O(N)的时间复杂度的情况下,空间复杂度可以做到O(1),设置如下几个变量

    ListNode sH = null; // 小于区域的头结点
    ListNode sT = null; // 小于区域的尾结点
    ListNode eH = null; // 等于区域的头结点
    ListNode eT = null; // 等于区域的尾结点
    ListNode mH = null; // 大于区域的头结点
    ListNode mT = null; // 大于区域的尾结点
    ListNode next; // 记录遍历到的结点的下一个结点
    

    接下来开始遍历链表,进行主流程处理,伪代码如下

    while (head != null) {
        next = head.next;
        // 如果head.val < pivot,则通过sH,sT构造小于区域的链表
        // 如果head.val == pivot,则通过eH,eT构造小于区域的链表
        // 如果head.val > pivot,则通过mH,mT构造小于区域的链表
        head = next;
    }
    // 把三个区域的链表串联起来即可。
    

    构造每个区域的链表的时候,还要考虑链表是第一次被构造还是已经构造了,以小于区域的链表为例,如果是第一次构造,则sH == null,此时需要把sHsT同时初始化:

    if (sH == null) {
        sH = head;
        sT = head;
    } 
    

    如果不是第一次构造,则

    sT.next = head;
    sT = head;
    

    开始区域的尾指针直接指向当前结点,然后把尾指针设置未当前结点即可。

    其他两个区域的链表处理方式同理。

    最后需要把三个区域的链表连接起来:

            // 小于区域的尾巴,连等于区域的头,等于区域的尾巴连大于区域的头
            if (sT != null) { // 如果有小于区域
                sT.next = eH;
                eT = eT == null ? sT : eT; // 下一步,谁去连大于区域的头,谁就变成eT
            }
            // all reconnect
            if (eT != null) { // 如果小于区域和等于区域,不是都没有
                eT.next = mH;
            }
            // 如果小于区域有,小于区域的头就是最终链表的头
            // 如果小于区域没有,等于区域的头有,则等于区域的头就是最终链表的头
            // 如果小于和等于区域都没有,则大于区域的头就是最终链表的头
            return sH != null ? sH : (eH != null ? eH : mH);
    

    完整代码见

    public class Code_PartitionList {
    
        public static class ListNode {
            public int val;
            public ListNode next;
    
            public ListNode(int data) {
                this.val = data;
            }
        }
    
    
        public static ListNode listPartition2(ListNode head, int pivot) {
            ListNode sH = null; // small head
            ListNode sT = null; // small tail
            ListNode eH = null; // equal head
            ListNode eT = null; // equal tail
            ListNode mH = null; // big head
            ListNode mT = null; // big tail
            ListNode next; // save next node
            // every node distributed to three lists
            while (head != null) {
                next = head.next;
                head.next = null;
                if (head.val < pivot) {
                    if (sH == null) {
                        sH = head;
                        sT = head;
                    } else {
                        sT.next = head;
                        sT = head;
                    }
                } else if (head.val == pivot) {
                    if (eH == null) {
                        eH = head;
                        eT = head;
                    } else {
                        eT.next = head;
                        eT = head;
                    }
                } else {
                    if (mH == null) {
                        mH = head;
                        mT = head;
                    } else {
                        mT.next = head;
                        mT = head;
                    }
                }
                head = next;
            }
            // 小于区域的尾巴,连等于区域的头,等于区域的尾巴连大于区域的头
            if (sT != null) { // 如果有小于区域
                sT.next = eH;
                eT = eT == null ? sT : eT; // 下一步,谁去连大于区域的头,谁就变成eT
            }
            // all reconnect
            if (eT != null) { // 如果小于区域和等于区域,不是都没有
                eT.next = mH;
            }
            // 如果小于区域有,小于区域的头就是最终链表的头
            // 如果小于区域没有,等于区域的头有,则等于区域的头就是最终链表的头
            // 如果小于和等于区域都没有,则大于区域的头就是最终链表的头
            return sH != null ? sH : (eH != null ? eH : mH);
        }
    }
    

    解决了链表的荷兰国旗问题,那么原题中的链表 Partition 问题,就迎刃而解了。

    由于是 Partition,所以不存在等于区域,只需要考虑小于区域和大于区域,只需要设置如下几个变量即可。

    ListNode sH = null; // 小于区域的头
    ListNode sT = null; // 小于区域的尾
    ListNode mH = null; // 大于区域的头
    ListNode mT = null; // 大于区域的尾
    ListNode cur = head; // 当前遍历到的结点
    

    接下来开始遍历链表,进行主流程处理,伪代码如下

    while (cur != null) {
        // 如果head.val < pivot,则通过sH,sT构造小于区域的链表
        // 如果head.val > pivot,则通过mH,mT构造小于区域的链表
        cur = cur.next;
    }
    // 把两个区域的链表串联起来即可。
    

    构造每个区域的链表的时候和上述荷兰国旗问题一样。

    最后需要把两个区域的链表连接起来:

    
            if (mT != null) {
                // 大于区域的尾置空
                mT.next = null;
            }
            
            if (sT != null) {
                // 小于区域的尾置空
                sT.next = null;
            }
            // 经过上述操作,两个链表断开连接
            if (sH == null) {
                // 小于区域的头为空,说明只有大于区域
                return mH;
            }
            // 小于区域的头不为空,小于区域的尾一定也不为空,直接把小于区域的尾连上大于区域的头即可。
            sT.next = mH;
            return sH;
    

    完整代码见

    class Solution {
        public static ListNode partition(ListNode head, int x) {
            ListNode sH = null;
            ListNode sT = null;
            ListNode mH = null;
            ListNode mT = null;
            ListNode cur = head;
            while (cur != null) {
                if (cur.val < x) {
                    if (sH == null) {
                        sH = cur;
                    } else {
                        sT.next = cur;
                    }
                    sT = cur;
                } else {
                    // cur.val >= x
                    // 都放到大于等于区域
                    if (mH == null) {
                        mH = cur;
                    } else {
                        mT.next = cur;
                    }
                    mT = cur;
                }
                cur = cur.next;
            }
            if (mT != null) {
                mT.next = null;
            }
            if (sT != null) {
                sT.next = null;
            }
            if (sH == null) {
                return mH;
            }
            sT.next = mH;
            return sH;
        }
    }
    

    更多

    算法和数据结构笔记

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册