【链表】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大或等于的节点连成另一条链，然后把两条链连起来。注意一下边界情况(某条链为空)。

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/**

 * @param {ListNode} head

 * @param {number} x

 * @return {ListNode}

 */

var partition = function(head, x) {

    if(head==null||head.next==null){

        return head;

    }

    var lHead=null;

    var gHead=null;

    var p=head,pl=null,pg=null,temp=null;

    while(p){

        if(p.val<x){

            if(lHead==null){

                lHead=p;

                pl=p;

            }else{

                pl.next=p;

                pl=pl.next;

            }

        }else{

            if(gHead==null){

                gHead=p;

                pg=p;

            }else{

                pg.next=p;

                pg=pg.next;

            }

        }

        temp=p;

        p=p.next;

        temp.next=null;

    }

    if(pg!=null){

        pg.next=null;

    }

    if(lHead!=null){

        pl.next=gHead;

        return lHead;

    }else{

        return gHead;

    }

};

巴特西

【链表】Partition List

最新文章

热门文章