Partition List

原题: 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;
        }
    };
  • 回复
隐藏