leetcode86.分隔链表

leetcode86.分隔链表

二月 23, 2020

leetcode86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路

遍历链表，把大于x的节点存在链表1中，小于x的链表存在链表2中，最后把两个链表合并就行了。（分类是双指针，但是我并没有看到双指针啊）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode partition(ListNode head, int x) {
        ListNode now=head;
        ListNode head1=new ListNode(-1);
        ListNode head2=new ListNode(-1);
        ListNode tmp1=head1,tmp2=head2;
        while(now!=null){
            if(now.val<x){
                tmp1.next=new ListNode(now.val);            
                tmp1=tmp1.next;
            }else{
                tmp2.next=new ListNode(now.val);
                tmp2=tmp2.next;
            }
            now=now.next;
        }                 
        tmp1.next=head2.next;
        head=head1.next;
        return head;
    }

leetcode 15/100