题目:86. 分隔链表
思路:双指针,时间复杂度0(n)。
双指针来维护小于x的链表和不小于x的链表即可,后面将两个链表连起来即可。
C++版本:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *p =new ListNode(0);
ListNode *q =new ListNode(0);
ListNode *p0=p,*q0=q;
while(head!=nullptr){
if(head->val<x){
p->next=head;
p=p->next;
}else{
q->next=head;
q=q->next;
}
head=head->next;
}
p->next=q0->next;
q->next=nullptr;
return p0->next;
}
};
JAVA版本:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode p =new ListNode(0);
ListNode q =new ListNode(0);
ListNode p0=p,q0=q;
while(head!=null){
if(head.val<x){
p.next=head;
p=p.next;
}else{
q.next=head;
q=q.next;
}
head=head.next;
}
p.next=q0.next;
q.next=null;
return p0.next;
}
}
GO版本:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
p,q:=&ListNode{Val:0},&ListNode{Val:0}
p0,q0:=p,q
for head!=nil {
if head.Val<x {
p.Next=head
p=p.Next
}else{
q.Next=head
q=q.Next
}
head=head.Next
}
p.Next=q0.Next
q.Next=nil
return p0.Next
}