LeetCode刷题笔记（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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

题意分析： 

给定一个链表和一个x值，将链表中所有小于x值的节点放在大于或等于x值的节点之前，且应该保证原始节点的相对顺序不变。

解答如下：

方法一（常规法）

先用pre指针找到一个大于或等于x值的节点，然后用cur指针找到小于x值的节点，再新建一个tmp指针指向小于x值的节点，并配合cur指针进行节点换位，直至跳出while循环，返回新链表的头节点。

注：只有cur -> next不为空，才可以使用cur -> next -> val，所以需要对cur -> next是否为空进行判断。

class Solution{
public:
    ListNode* partition( ListNode* head, int x ){
        ListNode* dummy = new ListNode( -1 );               //常规操作
        dummy -> next = head;
        ListNode* pre = dummy;
        while ( pre -> next && pre -> next -> val < x ) pre = pre -> next; //找到大于或等于x值的节点
        ListNode* cur = pre;
        while ( cur -> next ){
            if( cur -> next -> val < x )                    //找到小于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;
    }
};

 

提交后的结果如下：  

 

方法二（新链表法）

从原链表中取出所有小于x值的节点并组成一个新的链表，所以原链表中剩余的节点值都大于或等于x值，最后将原链表直接连在新链表后，即为所求新链表。

class Solution{
public:
    ListNode* partition( ListNode* head, int x ){
        ListNode* dummy = new ListNode( -1 );          //常规操作
        dummy -> next = head;
        ListNode* cur = dummy;
        ListNode* newdummy = new ListNode( -1 );       //新建链表
        ListNode* p = newdummy;
        while ( cur -> next ){                   
            if ( cur -> next -> val < x )        //取出所有小于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;
    }
    
};

提交后的结果如下：  

 

 

日积月累，与君共进，增增小结，未完待续。