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條評論
主站蜘蛛池模板: 免费一看一级欧美 | 精品日韩一区二区三区视频 | 久久性生活片 | 国产高清久久 | 91九色露脸 | 中文字幕一区二区三区精彩视频 | 天天草天天操 | 99re热这里只有精品视频 | 狠狠狠色丁香婷婷综合久久五月 | 成人精品一区二区激情 | 日韩欧美综合在线 | 精品哟哟哟国产在线观看不卡 | 亚洲欧美日韩精品中文乱码 | 亚洲一区二区三区网站 | 四虎院影永久在线观看 | 97在线视频观看 | 国产精品二区页在线播放 | 狠狠色丁香久久婷婷综合_中 | 日本一级~片免费永久 | 久青草中文字幕精品视频 | 爆操白虎 | 欧美日韩色黄大片在线视频 | 久久中文亚洲国产 | 青青青青在线成人视99 | 国产农村一一级特黄毛片 | 2021国产成人综合亚洲精品 | 中文字幕在线看视频一区二区三区 | 欧美韩国日本在线 | 国产欧美一区视频在线观看 | 奇米影视奇米色 | 国产精品99re | 国产一级毛片外aaaa | 香蕉尹人| 寡妇一级a毛片免费播放 | 国产视频二区在线观看 | 国产精品香蕉在线一区二区 | 久久综合亚洲一区二区三区 | 亚洲欧美一区二区三区麻豆 | 免费看黄色的网站 | 色香蕉网站 | 欧美狠狠干 |