题意概述

• 给定一个单链表和一个整数x
• 将链表中小于x的数划分链表左侧，其他数按序排在后面

方法一：一次遍历

思路与具体做法

• 循环一遍原先链表，
• 双指针分别找遍历过程中小于的元素，并将其放入list1链表中
• 和找遍历过程中大于的元素，并将其放入list2链表中
• 之后将链表连接起来即可

	class Solution {
	public:
	    ListNode* partition(ListNode* head, int x) {
	        ListNode *list1=new ListNode(0),*list2=new ListNode(0);//新建链表头结点 
	        ListNode *p=list1,*q=list2;//指向新建链表 
	        while(head){//遍历原来的链表 
	        	if(head->val<x){
	        		p->next=head;//p指向当前结点，并令p指针后移 
	        		p=p->next;
				}else{
	        		q->next=head;//q指向当前结点，并令q指针后移 
	        		q=q->next;				
				}
				head=head->next;
			}
			p->next=list2->next;//将两个链表连上 
			q->next=NULL;//链表尾置为NULL 
			return list1->next;
	    }
	};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历一次长度为n的链表
• 空间复杂度：$O(1)O(1)$，仅仅新建了2个结点

方法二：两次遍历

思路与具体做法

• 循环两遍原先链表，
• 第一遍找小于元素的结点，并将其放入list链表中
• 第二遍找大于等于元素的结点，并将其放入list链表中

	class Solution {
	public:
	    ListNode* partition(ListNode* head, int x) {
	        ListNode *list=new ListNode(INT_MIN);//新建链表头结点 
	        ListNode *p=list,*head2=head;//指向新建链表 
	        while(head){//遍历原来的链表 
	        	if(head->val<x){
	        		p->next=new ListNode(head->val);//p指向当前结点，并令p指针后移 
	        		p=p->next;
				}
				head=head->next;
			}
	        while(head2){//遍历原来的链表 
	        	if(head2->val>=x){
	        		p->next=new ListNode(head2->val);//p指向当前结点，并令p指针后移 
	        		p=p->next;
				}
				head2=head2->next;
			}
			p->next=NULL;//链表尾置为NULL 
			return list->next;
	    }
	};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历两次长度为n的链表
• 空间复杂度：$O(n)O(n)$，新建了总长度为n的链表