Partition List-K6K4.com

原题： https://leetcode.com/problems/partition-list/description/
题意： 给定一个单链表和一个x，把链表中小于x的放到前面，大于等于x的放到后面。
约定：（1）要求每部分元素的原始相对位置不变。
例子：

Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

标签： partition、放到、单链、list、原始、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-11 13:00:48 1楼#1层

解法一：

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;
    }
};

Bingo

2017-08-11 13:01:06 2楼#1层

解法二：

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;
    }
};

取消

回复

推荐圈子

LeetCode交流圈