daily leetcode - partition-list - !

题目地址

https://leetcode.com/problems/partition-list/

题目描述

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.

思路

这道题要求我们划分链表,把所有小于给定值的节点都移到前面,大于该值的节点顺序不变,相当于一个局部排序的问题。那么可以想到的一种解法是首先找到第一个大于或等于给定值的节点,用题目中给的例子来说就是先找到 4,然后再找小于 3 的值,每找到一个就将其取出置于 4 之前即可,代码如下:

解法一

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;;
        while (pre->next && pre->next->val < x) pre = pre->next;
        cur = pre;
        while (cur->next) {
            if (cur->next->val < x) {
                ListNode *tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = pre->next;
                pre->next = tmp;
                pre = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

这种解法的链表变化顺序为:

1 -> 4 -> 3 -> 2 -> 5 -> 2

1 -> 2 -> 4 -> 3 -> 5 -> 2

1 -> 2 -> 2 -> 4 -> 3 -> 5

此题还有一种解法,就是将所有小于给定值的节点取出组成一个新的链表,此时原链表中剩余的节点的值都大于或等于给定值,只要将原链表直接接在新链表后即可,代码如下:

解法二

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-1);
        ListNode *newDummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy, *p = newDummy;
        while (cur->next) {
            if (cur->next->val < x) {
                p->next = cur->next;
                p = p->next;
                cur->next = cur->next->next;
                p->next = NULL;
            } else {
                cur = cur->next;
            }
        }
        p->next = dummy->next;
        return newDummy->next;
    }
};

此种解法链表变化顺序为:

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2

New:

Original: 4 -> 3 -> 2 -> 5 -> 2

New:  1

Original: 4 -> 3 -> 5 -> 2

New:  1 -> 2

Original: 4 -> 3 -> 5

New:  1 -> 2 -> 2

Original:

New:  1 -> 2 -> 2 -> 4 -> 3 -> 5

思路2

  • 设定两个虚拟节点,dummyHead1用来保存小于该值的链表,dummyHead2来保存大于等于该值的链表

  • 遍历整个原始链表,将小于该值的放于dummyHead1中,其余的放置在dummyHead2中

遍历结束后,将dummyHead2插入到dummyHead1后面

mark

(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)

关键点解析

  • 链表的基本操作(遍历)
  • 虚拟节点dummy 简化操作
  • 遍历完成之后记得currentL1.next = null;否则会内存溢出

如果单纯的遍历是不需要上面操作的,但是我们的遍历会导致currentL1.next和currentL2.next
中有且仅有一个不是null, 如果不这么操作的话会导致两个链表成环,造成溢出。

代码

  • 语言支持: Javascript,Python3
/*
 * @lc app=leetcode id=86 lang=javascript
 *
 * [86] Partition List
 *
 * https://leetcode.com/problems/partition-list/description/
 *
 * algorithms
 * Medium (36.41%)
 * Total Accepted:    155.1K
 * Total Submissions: 425.1K
 * Testcase Example:  '[1,4,3,2,5,2]\n3'
 *
 * 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.
 * 
 * Example:
 * 
 * 
 * Input: head = 1->4->3->2->5->2, x = 3
 * Output: 1->2->2->4->3->5
 * 
 * 
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    const dummyHead1 = {
        next: null
    }
    const dummyHead2 = {
        next: null
    }
    
    let current = {
        next: head
    };
    let currentL1 = dummyHead1;
    let currentL2 = dummyHead2;
    while(current.next) {
        current = current.next;
        if (current.val < x) {
            currentL1.next = current;
            currentL1 = current;
        } else {
            currentL2.next = current;
            currentL2 = current;
        }
    }
    
    currentL2.next = null;
 
    currentL1.next = dummyHead2.next;

    return dummyHead1.next;
};

Python3 Code:

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        """在原链表操作,思路基本一致,只是通过指针进行区分而已"""
        # 在链表最前面设定一个初始node作为锚点,方便返回最后的结果
        first_node = ListNode(0)
        first_node.next = head
        # 设计三个指针,一个指向小于x的最后一个节点,即前后分离点
        # 一个指向当前遍历节点的前一个节点
        # 一个指向当前遍历的节点
        sep_node = first_node
        pre_node = first_node
        current_node = head
        
        while current_node is not None:
            if current_node.val < x:
                # 注意有可能出现前一个节点就是分离节点的情况
                if pre_node is sep_node:
                    pre_node = current_node
                    sep_node = current_node
                    current_node = current_node.next
                else:
                    # 这段次序比较烧脑
                    pre_node.next = current_node.next
                    current_node.next = sep_node.next
                    sep_node.next = current_node
                    sep_node = current_node
                    current_node = pre_node.next
            else:
                pre_node = current_node
                current_node = pre_node.next
        
        return first_node.next

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - partition-list - !
文章作者: lonuslan
文章链接: https://louislan.com/articles/2020/03/07/1583560618679.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LouisLan
    评论
    0 评论
avatar

取消