86. Partition List（分隔链表）

2018-12-04 本文已影响17人 Aiewing

题目

解答

大致解析题目意思，就是把一个链表分成两个部分，但是相对位置不变化，第一想法就是直接遍历一次，分别使用两个新链表存起来，最后拼接在一起，就是需要的最后答案了。

1.创建左链表和右链表，并创建记录当前位置的节点。
2.取出原链表中的节点，被目标参数比较，如果是小于目标参数的，就放到左链表最后，并移动左链表当前节点到下个节点；如果是大于等于目标参数的，就放到右链表最后，并移动右链表当前节点到下个节点，最后移动原链表当前节点到下个节点。
3.重复步骤2，直到原链表所有的数据都被取完。
4.最后拼接两个链表，最后链表就是所需要的链表了

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 左边链表头
        ListNode *leftHeadNode = new ListNode(0);
        // 右边链表头
        ListNode *rightHeadNode = new ListNode(0);
        // 左边链表的当前位置
        ListNode *leftCurrentNode = leftHeadNode;
        // 右边链表的当前位置
        ListNode *rightCurrentNode = rightHeadNode;
        while (head != NULL) {
            if (head->val < x) {
                // 把小于x的节点放到左链表最后 并移动当前节点到下个节点
                leftCurrentNode->next = head;
                leftCurrentNode = leftCurrentNode->next;
            } else {
                // 把大于等于x的节点放到右链表最后 并移动当前节点到下个节点
                rightCurrentNode->next = head;
                rightCurrentNode = rightCurrentNode->next;
            }
            head = head->next;
        }
        // 拼接两个列表
        leftCurrentNode->next = rightHeadNode->next;
        rightCurrentNode->next = NULL;
        return leftHeadNode->next;
    }
};

以上代码时间复杂度为 $O(n)$ ，创建了两个新的链表，空间复杂度为 $O(n)$ 。

以上代码时间复杂度已经很低了，但是空间复杂度还有一定的优化的空间，之前我们创建了两个链表，现在考虑能不能就在原来的链表上操作，不创建新的链表呢？
这个我还没想出来，但是我们可以创建一个链表，让另外一部分在原来的链表上操作，最后拼接起来。

1.创建左链表和原链表的父节点，并创建记录当前位置的节点。
2.取出原链表中的节点，被目标参数比较，如果是小于目标参数的，就放到左链表最后，移动左链表当前节点到下个节点，并把当前节点从原链表中删除；如果是大于等于目标参数的，直接移动原链表当前节点到下个节点。
3.重复步骤2，直到原链表所有的数据都被取完。
4.最后拼接两个链表，最后链表就是所需要的链表了

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 左边链表头
        ListNode *leftHeadNode = new ListNode(0);
        // 原节点的父节点
        ListNode *fatherHeadNode = new ListNode(0);
        // 为了让第一个节点拥有父节点 删除节点的时候容易一点 所以为原链表设置一个父节点
        fatherHeadNode->next = head;
        // 左边链表的当前位置
        ListNode *leftCurrentNode = leftHeadNode;
        // 原链表的当前位置
        ListNode *headCurrentNode = fatherHeadNode;
        while (headCurrentNode->next != NULL) {
            // 判断当前的值
            if (headCurrentNode->next->val < x) {
                // 把小于x的节点放到左链表最后 并移动当前节点到下个节点
                leftCurrentNode->next = headCurrentNode->next;
                leftCurrentNode = leftCurrentNode->next;
                // 删除当前的节点
                headCurrentNode->next = headCurrentNode->next->next;
                leftCurrentNode->next = NULL;
            } else {
                // 当前节点不变 移动当前节点到下个节点
                headCurrentNode = headCurrentNode->next;
            }
        }
        // 拼接两个列表
        leftCurrentNode->next = fatherHeadNode->next;
        return leftHeadNode->next;
    }
};

以上代码时间复杂度为 $O(n)$ ，但是只创建了一个新的链表，虽然空间复杂度还是为 $O(n)$ ，但是在使用的空间上比之前的算法减少了一点。

在朋友的提示下，终于想到了时间复杂度 $O(1)$ 的解法，说起来也简单，之前怎么就没有想到呢？

原理就是通过和目标参数的比较，把小于目标参数的放在链表的前面，把大于等于目标参数的放在链表的后面，这样相当于链表就被分割成了两部分，最后把两部分拼接起来就好了

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 左边链表头
        ListNode *leftHeadNode = new ListNode(0);
        // 右边链表头
        ListNode *rightHeadNode = new ListNode(0);
        rightHeadNode->next = head;
        // 左边链表的当前位置
        ListNode *leftCurrentNode = leftHeadNode;
        // 右边链表的当前位置
        ListNode *rightCurrentNode = rightHeadNode;
        while (rightCurrentNode->next != NULL) {
            if (rightCurrentNode->next->val < x) {
                // 移除这个点 并重新拼接原来的节点
                leftCurrentNode->next = rightCurrentNode->next;
                leftCurrentNode = leftCurrentNode->next;
                rightCurrentNode->next = rightCurrentNode->next->next;
            } else {
                rightCurrentNode = rightCurrentNode->next;
            }
        }
        leftCurrentNode->next = rightHeadNode->next;
        return leftHeadNode->next;
    }
};

以上代码时间复杂度为 $O(n)$ ，空间复杂度还是为 $O(1)$ 。

86. Partition List（分隔链表）

题目

解答

猜你喜欢

热点阅读