链表

链表是有序的，不一定是连续的存储空间。

反转链表

function ReverseList(pHead)
{
    // 首先遍历这个链表
    let arr = [];
    let node = pHead;
    while(pHead) {
        arr.push(pHead.val);
        pHead = pHead.next;
    }
    let result = node;
    while(node) {
        node.val = arr.pop();
        node = node.next;
    }
    return result;
}
module.exports = {
    ReverseList : ReverseList
};

合并两个有序链表

var mergeTwoLists = function(l1, l2) {
 if(l1===null){
   return l2
}
  else if(l2===null){
    return l1
  }
  else if(l1.val<=l2.val){
    l1.next=mergeTwoLists(l1.next,l2)
  }
  else (l2.val<l1.val){
    l2.next=mergeTwoLists(l1,l2.next)
  }

链表指定区间反转

function reverseBetween( head ,  m ,  n ) {
    // write code here
    if(head===null||head.next===null||m===n) 
        return head
    let res=new ListNode(-1)
    res.next=head
    let cur=res,temp
    for(let i=0;i<m-1;i++){
        cur=cur.next
    }
    temp = cur.next;
    for(let i=0; i<n-m; i++) {
        let next = temp.next;
        temp.next = next.next;
        next.next = cur.next;
        cur.next = next;
    }
    return res.next
}
module.exports = {
    reverseBetween : reverseBetween
};

链表中的节点每k个一组翻转

function reverse(left,right){
    let pre=right
    while(left!==right){
        let next=left.next
        left.next=pre
        pre=left
        left=next
    }
    return pre

}
function reverseKGroup( head ,  k ) {
    // write code here
    let node=head
    if(head===null) 
        return head
    for(let i=0;i<k;i++){
        if(!node)
            return head
        node=node.next

    }
    let res=reverse(head,node)
    head.next=reverseKGroup(node,k)
    return res

}

module.exports = {
    reverseKGroup : reverseKGroup,
    reverse:reverse
};

链表中环的入口结点

function EntryNodeOfLoop(pHead)
{
    if(pHead==null||pHead.next==null){
        return null
    }
    let map=[]
    while(pHead){
        if(map.indexOf(pHead)!==-1){
            return pHead
        }
        map.push(pHead)
        pHead=pHead.next
    }
    return null
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

链表中倒数最后k个结点

function FindKthToTail( pHead ,  k ) {
    // write code here
    let slow=pHead
    let fast=pHead
    while(fast!==null){
        if(k<=0){
            slow=slow.next
        }
        k--
        fast=fast.next
    }
    if(k<=0){
    return slow
    }
    else
        return null

}
module.exports = {
    FindKthToTail : FindKthToTail
};

删除链表的倒数第n个节点

var removeNthFromEnd = function(head, n) {
let node=new ListNode(null)
node.next=head
let slow=node;fast=node
for(n;n>0;n--){
    fast=fast.next
}
while(fast.next){
    slow=slow.next
    fast=fast.next
}
slow.next=slow.next.next
return node.next
};

环形链表

//哈希法
const hasCycle = (head) => {
    let map = new Map();
    while (head) {
        if (map.has(head)) return true;
        map.set(head, true); // 存的是节点的地址引用，而不是节点值
        head = head.next;
    }
    return false;
};
//标志法
const hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
};
//偷懒法
const hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true;
    }
};

两个链表的第一个公共节点

function FindFirstCommonNode(pHead1, pHead2)
{
    let map=[]
   while(pHead1!==null){
       map.push(pHead1)
       pHead1=pHead1.next
   }
    while(pHead2!==null){
        if(map.indexOf(pHead2)!==-1)
            return pHead2
        pHead2=pHead2.next
    }
    return null
    // write code here
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};

单链表的排序

function sortInList( head ) {
    // write code here
    if (head===null||head.next===null) return head
    let move=head;
    while(move.next!=null){
        let temp=move.next;
        while(temp!=null){
            if(temp.val<move.val){
                let a=temp.val
                temp.val=move.val
                move.val=a
            }
            temp=temp.next
        }
        move=move.next
    }
    return head
}
module.exports = {
    sortInList : sortInList
};

判断一个链表是否为回文结构

function reverse(node){
    let pre=null
//     pre.next=node
    while(node!==null){
        let next=node.next
        node.next=pre
        pre=node
        node=next
    }
    return pre
}
function isPail( head ) {
    // write code here
    if(head===null||head.next===null) return true
    let slow=head
    let fast=head
    while(fast!==null&&fast.next!==null){
        slow=slow.next
        fast=fast.next.next
    }
    if(fast!==null)
        slow=slow.next
    slow=reverse(slow)
    fast=head
    while(slow!=null){
        if(fast.val!=slow.val)
            return false
        slow=slow.next
        fast=fast.next
    }
    return true
}
module.exports = {
    isPail : isPail,
    reverse:reverse
};

链表的奇偶重排

function oddEvenList( head ) {
    // write code here
    if(head===null||head.next===null)
        return head
    let evenhead=head.next
//     let even=evenhead
//     let node=head.next
    let odd=head
    let even=evenhead
    while(even!==null&&even.next!==null){
        odd.next=even.next
        odd=odd.next
        even.next=odd.next
        even=even.next
    }
    odd.next=evenhead
    return head
}
module.exports = {
    oddEvenList : oddEvenList
};

删除有序链表的重复元素-1

function deleteDuplicates( head ) {
    let map=[]
    if(head===null||head.next===null)
        return head
    let node=head
    let fast=head.next
    map[head.val]=1
    while(fast!==null){
        if(!map[fast.val]){
            map[fast.val]=1
            node=node.next
            fast=fast.next
        }
        else
            node.next=fast.next
            fast=node.next
    }
    return head
    // write code here
}
module.exports = {
    deleteDuplicates : deleteDuplicates
};

分割链表

var partition = function(head, x) {
    let left=new ListNode(null)
     let start=left
    let right=new ListNode(null)
    let add=right
    while(head){
        if(head.val<x){
            left.next=head
            left=left.next
        }
        else {
              right.next=head
              right=right.next
        }
        head=head.next
    }
    right.next=null
    left.next=add.next
    return start.next
};

移除重复节点

var removeDuplicateNodes = function(head) {
    let set=new Set()
    let node=new ListNode(0)
     let res=head
     node.next=head
     while(head){
         if(set.has(head.val)){
             node.next=head.next
             head=head.next
         }
         else{
             set.add(head.val)
              node=node.next
              head=head.next
         }
     }
     return res
};