【链表】 LeetCode86. 分隔链表

绝地灬酷狼 2022-12-02 13:38 159阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]

### 解答 ###

struct ListNode { 
      int value;
      ListNode* next;
    
      ListNode(int val)
        : value(val)
        , next(nullptr) { 
      }
    };
    
    void PrintList(ListNode* list) { 
      while (list != nullptr) { 
        std::cout << list->value << ", ";
        list = list->next;
      }
    
      std::cout << std::endl;
    }
    
    // 巧用临时空的头结点。
    // 思路：将小于x的结点拼接成一个链表，将大于等于x的结点拼接成另一个链表，最后将两条链表连接。
    ListNode* Partition(ListNode* head, int x) { 
      ListNode less_list_head(-1);
      ListNode* less_list_node = &less_list_head;
    
      ListNode more_list_head(-1);
      ListNode* more_list_node = &more_list_head;
    
      while (head != nullptr) { 
        if (head->value < x) { 
          less_list_node->next = head;
          less_list_node = head;
        } else { 
          more_list_node->next = head;
          more_list_node = head;
        }
    
        head = head->next;
      }
    
      less_list_node->next = more_list_head.next;
      more_list_node->next = nullptr;  // 注意处理最后一个结点。
    
      return less_list_head.next;
    }
    
    void TestCase() { 
      ListNode node1(1);
      ListNode node2(4);
      ListNode node3(3);
      ListNode node4(4);
      ListNode node5(2);
      ListNode node6(6);
      ListNode node7(9);
      ListNode node8(7);
    
      node1.next = &node2;
      node2.next = &node3;
      node3.next = &node4;
      node4.next = &node5;
      node5.next = &node6;
      node6.next = &node7;
      node7.next = &node8;
    
      PrintList(&node1);
      ListNode* new_head = Partition(&node1, 4);
      PrintList(new_head);
    }
    
    int main() { 
      TestCase();
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/61ab7a478c6244aa84930bb5b750cccd.png