每日一题2. 分隔链表

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

大于或等于 x 的节点之前 每个节点的初始相对位置

思路

测试

不存在小于x的数值

代码

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
       
       if(head ==NULL ||head->next==NULL)
       {
           return head;
       }
       ListNode* head1=NULL;
       ListNode* small=NULL;
       
       ListNode* big=NULL;
       ListNode* head2=NULL;
       
       while(head)
       {
           if(head->val<x)
           {
              if(small ==NULL)
              {  
                head1=head;
                small=head;
              }else
              {
                  small->next=head;
                  small=head;//
              }
           }else
           {
              if(big ==NULL)
              {  
                head2=head;
                big=head;
              }else
              {
                  big->next=head;
                  big=head;//
              }
           }

           head=head->next;//遍历过程中，head本身没有发生变化 ，对比翻转链表。
       }
       //优化 头节点 不用判断small null还是非null
       if(small ==NULL)
       {
          head1=head2;
       }else
       {
           small->next=head2;
       }
       if(big)
       {
         big->next=NULL;
       }
       

       return head1;
    }
};

总结：

链表操作不是移动记录。而是修改指针
效率还是很高的。
定义链表常用结构 定义head 和tail 这样
这样操作很便利