链表常见面试题

function FindKthToTail(head, k) {
    if (head == null) {
        return false;
    }
    var currNode = head;
    var arr = [];
    while (currNode != null) {
        arr.push(currNode);
        currNode = currNode.next;
    }
    return arr[arr.length - k];
}

function Merge(pHead1, pHead2) {
    if (pHead1 == null) {
        return pHead2;
    } else if (pHead2 == null) {
        return pHead1;
    }
    var result = {};
    if (pHead1.val < pHead2.val) {
        result = pHead1;
        result.next = Merge(pHead1.next, pHead2);
    } else {
        result = pHead2;
        result.next = Merge(pHead1, pHead2.next);
    }
    return result;
}

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/
function Clone(pHead) {
    if (!pHead) {
        return null;
    }
    var newHead = new RandomListNode(pHead.label);
    newHead.random = pHead.random;
    newHead.next = Clone(pHead.next);
    return newHead;
}

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    var p1=pHead1;
    var p2=pHead2;
    while(p1!=p2){
        p1=p1==null?pHead2:p1.next;
        p2=p2==null?pHead1:p2.next;
    }
    return p1;
}

function EntryNodeOfLoop(pHead)
{
    // write code here
    if(pHead == null){
        return 1;
    }
    if(pHead.next == null){
        return null;
    }
    var fast = pHead;
    var slow = pHead;
    while(slow != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(fast == slow) break;
    }
     
    var p1 = slow;
    var p2 = pHead;
    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

function deleteDuplication(pHead) {
    var newHead = new ListNode('head');
    newHead.next = pHead;
    var pHead = newHead;
    var qHead = pHead.next;
    while (qHead) {
        while ((qHead.next != null) && (qHead.val == qHead.next.val)) {
            qHead = qHead.next;
        }
        //没移动
        if (pHead.next == qHead) {
            pHead = qHead;
            qHead = qHead.next;

        }
        //移动了
        else {
            qHead = qHead.next;
            pHead.next = qHead;

        }

    }
    return newHead.next;

}