LeetCode: Partition List

题目

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

分析

新建两个链表,第一个链表存放小于x的数,另一个存放大于等于x的数

从前往后遍历给定链表的每一个元素,并根据大小添加到上面创建的两个链表中。

最后把两个链表连接起来。

代码

class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        struct ListNode *less = new struct ListNode(0);
        struct ListNode *equal_or_greater = new struct ListNode(0);
        struct ListNode *ph, *pl, *pe;

        ph = head;
        pl = less;
        pe = equal_or_greater;
        //partition list into the two lists
        while (ph != NULL)
        {
            if (ph->val < x)
            {
                pl->next = ph;
                pl = pl->next;
                ph = ph->next;
            }
            else
            {
                pe->next = ph;
                pe = pe->next;
                ph = ph->next;
            }
        }

        //link the two lists
        pl->next = equal_or_greater->next;
        pe->next = NULL;

        //delete first node of the two lists
        struct ListNode *temp;
        temp = less;
        less = less->next;
        delete temp;
        delete equal_or_greater;

        return less;
    }
};

Note

一开始先删除头节点然后再连接两个链表,导致结果出问题了,原因在于删除头节点可能导致一个指针失效。

正确的做法应该是先连接链表再删除头节点。

参考

http://www.cnblogs.com/springfor/p/3862392.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40925997