【链表】Reorder List

题目：

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

思路：

先用快慢指针找到链表的中点，然后翻转链表后半部分，再和前半部分组合。需要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为NULL。

注意：后半部分可能比前半部分长，所以最后要判断一下是否将后半部分全部加入链表。

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/**

 * @param {ListNode} head

 * @return {void} Do not return anything, modify head in-place instead.

 */

var reorderList = function(head) {

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

        return;

    }

    var l=head,r=head,lpre=null;

    while(r!=null&&r.next!=null){

        lpre=l;

        l=l.next;

        r=r.next.next;

    }

    lpre.next=null;

    r=reverseList(l);

    var p=head,temp=null,tempr,tail=null;

    while(p!=null){

        temp=p.next;

        tempr=r;

        r=r.next;

        p.next=tempr;

        tail=p.next;

        tempr.next=temp;

        p=temp;

    }

    if(r!=null){

        tail.next=r;

    }

};

var reverseList = function(head) {

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

        return head;

    }

    var temp=null,pre=null,cur=null;

    pre=head;

    cur=pre.next;

    pre.next=null;

    while(cur!=null){

        temp=cur.next;

        cur.next=pre;

        pre=cur;

        cur=temp;

    }

    return pre;

};

巴特西

【链表】Reorder List

最新文章

热门文章