LeetCode: 86. 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.

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

题目大意： 给定一个值 x 和一个链表，将大于等于 x 的节点放在小于 x 的节点后面。要求每部分内部的节点相对位置不改变。

解题思路

分别将小于 x 的节点和大于等于 x 的节点用尾插法(顺序不变)串联在两个链表上，然后将两个链表按照要求链接。如：

• 链接第一个小于 x 的节点
  初始化状态：
  

  lessThanX = lessThanXTail = head:
  

  head = head->next:
  

  lessThanXTail->next = nullptr:
  

• 链接第二个小于 x 的节点
  初始状态：
  

  lessThanXTail->next = head:
  

  head = head->next:
  

  lessThanXTail = lessThanXTail->next:
  

  lessThanXTail->next = nullptr:
  

• 将大于等于 x 节点的链表加入小于 x 的链表
  初始状态:
  

lessThanXTail->next = notLessThanX:

AC 代码

/**
 * 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) {
        ListNode* lessThanX = nullptr, *lessThanXTail = nullptr;
        ListNode* notLessThanX = nullptr, *notLessThanXTail = nullptr;

        while(head != nullptr)
        {
            if(head->val < x)
            {
                if(lessThanX == nullptr)
                {
                    lessThanX = lessThanXTail = head;
                    head = head->next;
                    lessThanXTail->next = nullptr;
                }
                else
                {
                    lessThanXTail->next = head;
                    head = head->next;
                    lessThanXTail = lessThanXTail->next;
                    lessThanXTail->next = nullptr;
                }
            }
            else
            {
                if(notLessThanX == nullptr)
                {
                    notLessThanX = notLessThanXTail = head;
                    head = head->next;
                    notLessThanXTail->next = nullptr;
                }
                else
                {
                    notLessThanXTail->next = head;
                    head = head->next;
                    notLessThanXTail = notLessThanXTail->next;
                    notLessThanXTail->next = nullptr;
                }
            }
        }

        if(lessThanXTail == nullptr)
        {
            return notLessThanX;
        }
        else
        {
            lessThanXTail->next = notLessThanX;
            return lessThanX;
        }
    }
};