4->3->2->5->2andx=3,return1->2->2->4->3->5.思路:1.再用兩個node,一個指向所有小于x的,一個指向其他的,之后把兩個接在一起。接在一起需要注意large是否未移動過。/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*Li" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

leetcode[87] Partition List

系統 1621 0

題目:給定一個鏈表和一個數x,將鏈表中比x小的放在前面,其他的放在后頭。例如:

Given? 1->4->3->2->5->2 ?and? x ?= 3,
return? 1->2->2->4->3->5 .

思路:

1. 再用兩個node,一個指向所有小于x的,一個指向其他的,之后把兩個接在一起。接在一起需要注意large是否未移動過。

      
        /*
      
      
        *

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 
      
      
        */
      
      
        class
      
      
         Solution {


      
      
        public
      
      
        :

    ListNode 
      
      *partition(ListNode *head, 
      
        int
      
      
         x) 

    {

        
      
      
        if
      
       (head == NULL || head -> next == NULL) 
      
        return
      
      
         head;

        ListNode 
      
      *ans_small = 
      
        new
      
       ListNode(
      
        0
      
      
        ); 
        
          // 存小于x的
        
        

        ListNode 
      
      *ans_large = 
      
        new
      
       ListNode(
      
        0
      
      
        ); 
        
          // 存不小于x的
        
        

        ans_small 
      
      -> next =
      
         head;

        ans_large 
      
      -> next =
      
         head;

        ListNode 
      
      *small =
      
         ans_small;

        ListNode 
      
      *large =
      
         ans_large;

        ListNode 
      
      *cur =
      
         head;

        

        
      
      
        while
      
      
        (cur)

        {

            
      
      
        if
      
       (cur -> val <
      
         x)

            {

                small 
      
      -> next =
      
         cur;

                small 
      
      =
      
         cur;

                cur 
      
      = cur ->
      
         next;

            }

            
      
      
        else
      
      
        

            {

                large 
      
      -> next =
      
         cur;

                large 
      
      =
      
         cur;

                cur 
      
      = cur ->
      
         next;

            }

        }

        large 
      
      -> next = NULL; 
      
        //
      
      
         這個是為了防止large指向head的時候
      
      

        small -> next = ans_large ->
      
         next;

        head 
      
      =
      
         ans_small;

        delete ans_small, ans_large;

        
      
      
        return
      
       head ->
      
         next;

    }

};
      
    

2. 就創建一個node,這個node遇見比x小的就插入

        
          class
        
        
           Solution {


        
        
          public
        
        
          :

    ListNode 
        
        *partition(ListNode *head, 
        
          int
        
        
           x) 

    {

        
        
        
          if
        
         (head == NULL || head -> next == NULL) 
        
          return
        
        
           head;

        ListNode 
        
        *ans = 
        
          new
        
         ListNode(
        
          0
        
        
          );

        ans 
        
        -> next =
        
           head;

        ListNode 
        
        *small = ans; 
        
          //
        
        
           在它的后面插入小的
        
        

        ListNode *cur =
        
           head;

        ListNode 
        
        *pre = ans; 
        
          //
        
        
           cur的前一個指針,方便插入操作
        
        
          bool
        
         flag = 
        
          true
        
        ; 
        
          //
        
        
           true說明要插入的緊接著就是下一個,那就不用插入,加加就好
        
        
          while
        
        (cur !=
        
           NULL)

        {

            
        
        
          if
        
         (cur -> val < x && small -> next == cur) 
        
          //
        
        
           待插入的和之前小的相鄰就不用插入了
        
        
                      {

                pre 
        
        = pre ->
        
           next;

                cur 
        
        = cur ->
        
           next;

                small 
        
        = small ->
        
           next;

            }

            
        
        
          else
        
        
          if
        
         (cur -> val < x && small -> next != cur) 
        
          //
        
        
           不相鄰,插入
        
        
                      {

                ListNode 
        
        *tmpnext = small ->
        
           next;

                small 
        
        -> next =
        
           cur;

                small 
        
        =
        
           cur;

                cur 
        
        = cur ->
        
           next;

                small 
        
        -> next =
        
           tmpnext;

                pre 
        
        -> next =
        
           cur;

                flag 
        
        = 
        
          true
        
        
          ;

            }

            
        
        
          else
        
        
          if
        
         (cur -> val >=
        
           x)

            {

                flag 
        
        = 
        
          false
        
        
          ;

                cur 
        
        = cur ->
        
           next;

                pre 
        
        = pre ->
        
           next;

            }

        }

        head 
        
        =
        
           ans;

        delete ans;

        
        
        
          return
        
         head ->
        
           next;

    }

};
        
      
View Code

從第二個思路中知道了原來可以判斷連個node是否相等!這個之前以為不能那樣判斷的,原來可以用 if(node1 == node2)。多學一個知識點了。

leetcode[87] Partition List


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲男人的天堂久久香蕉网 | 香蕉综合网 | 国产毛片一级 | 高清欧美一区二区三区 | 国产精品四虎视频一区 | 成人最新午夜免费视频 | 日本中文字幕一区二区有码在线 | 久久99热久久精品动漫 | 狠狠干天天爽 | 九九网站 | 欧美精品日本一级特黄 | 久久久网久久久久合久久久久 | 亚洲欧美一区二区三区二厂 | 一级肉体毛片视频免费看看 | 亚洲成人一级 | 色综合亚洲天天综合网站 | 国产欧美亚洲精品综合在线 | 久久国产精品亚洲一区二区 | www.欧美视频| 久久久久久日本一区99 | 91久久国产 | 香蕉网站狼人久久五月亭亭 | 精品久久中文字幕 | 久久91| 神马毛片| 99久久中文字幕伊人情人 | 国内精品久久久久影院蜜芽 | 激情福利| 日韩欧美一级毛片精品6 | 亚洲最大黄色网址 | 91精品国产品国语在线不卡 | 嫩小xxxxx性bbbbb孕妇 | 亚洲第一黄色网址 | 国产精品久久久久久永久牛牛 | 97久久国产一区二区三区四区 | 免费观看欧美一级特黄 | 久久这里只有精品66re99 | 日本黄色绿像 | 亚洲国产一级a毛片 | 在线视频免费国产成人 | 香蕉爱视频 |