LeeCode-刷题日记-Day26

25. K 个一组翻转链表

思路：k个节点为一次翻转，则需要记录每次翻转的前驱节点和翻转的后继节点。同时翻转链表能提供头和尾方便链接。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let pre=new ListNode(0);
    pre.next=head;
    let p=pre;
    while(head){
        let tail=p;
        for(let i=0;i<k;++i){
            tail=tail.next;
            if(!tail)
                return pre.next;
        }
        let next=tail.next;
        [head,tail]=Reverse(head,tail);
        p.next=head;
        tail.next=next;
        p=tail;
        head=tail.next;
    }
    return pre.next;
};
function Reverse(head,tail){
        let last=tail.next;
        let p=head;
        while(last!==tail){
            let next=p.next;
            p.next=last;
            last=p;
            p=next;
        }
        return [tail,head];
    }

143. 重排链表

思路：将链表的每个节点加入队列中，每次从队头和队尾取元素。将他们连接起来。最后将最后一个节点的next至为null；

var reorderList = function(head) {
    if(head===null) return head;
    let p=head;
    let queue=[];
    while(p){
        queue.push(p);
        p=p.next;
    }
    while(queue.length>2){
        let pre=queue.shift();
        let tail=queue.pop();
        tail.next=pre.next;
        pre.next=tail;
    }
    queue[queue.length-1].next=null;
    return head;
};