题解 | #链表分割#C语言思路详解

一、思路呈现

 这道题目在原链表上进行操作将会异常复杂繁琐，所以我们的操作是创建两个新的链表：greater 和 less。

 greater后面跟大于x的结点，less后面跟小于x的结点。我们只需让less的尾结点接上greater的头结点即可。这样既实现了分割又保证原数据的顺序不被改变。

二、小技巧

创建哨兵结点

三、易错点

 注意最后一定要把greatertail->next置为NULL。为什么呢？我么设想一个极端的情况：原数据的最后一个结点（①结点）小于x，倒数第二个结点（②结点）大于x的，所以也就存在结点②指向结点①的的路径，形成了环形链表：

四、代码呈现

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        ListNode* greaterhead, *greatertail, *lesshead, *lesstail;
        greatertail = greaterhead = (ListNode*)malloc(sizeof(ListNode));
        lesstail = lesshead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* cur = pHead;
        
        while(cur)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
        }
        greatertail->next = NULL;
        lesstail->next = greaterhead->next;
        return lesshead->next;
    }
};

5、补充

当然我们也可以原地操作，只不过需要考虑的情况更多些：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* begin = new ListNode(0);
        ListNode* less = begin;
        begin->next = pHead;
        ListNode* cur = begin;
        while(cur && cur->next)
        {
            while(cur->next && cur->next->val < x)
            {
                if(&less->next != &cur->next)
                {
                    ListNode* move = cur->next;
                    cur->next = move->next;
                    move->next = less->next;
                    less->next = move;
                    less = less->next;
                }
                else 
                {
                    less = less->next;
                    cur = cur->next;
                }
            }
            cur = cur->next;
        }
        return begin->next;
    }
};