链表相关算法题

一、链表

（1）链表逆序206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：依次遍历链表节点，每遍历一个节点，反转一个节点。

var reverseList = function(head) {
    let newHead = null;
    let next = head;
    while(head){
        next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
};

（2）链表逆序进阶版92

 //分了三段式，找到头结点的前驱，尾节点的后继，把中间的部分反转，再拼接起来
var reverseBetween = function(head, left, right) {
    let preNode = null;
    let changeLen = right - left + 1;
    let next = null;
    let newHead = null;
    let result = head;
    while(head&&--left){
        preNode = head;
        head = head.next;
    }//头结点的前驱部分
    let reverseTailNode = head;//反转前的头结点；反转后的尾节点
    while(head&&changeLen){
        next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
        changeLen--;
    }
    reverseTailNode.next = head;
    if(preNode){
        preNode.next = newHead;
    }else{
        result = newHead
    }
    return result;
}

（3）求相交链表160

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解法一：利用set类，set类比较的是堆里面的地址，可以将headA插入到set类中，再用set类的has方法判断headB的节点是否在set类中。

var getIntersectionNode = function(headA, headB) {
    let setA = new Set();
    while(headA){
        setA.add(headA)
        headA = headA.next
    };
    while(headB){
        if(setA.has(headB)){
            return headB
        }
        headB = headB.next
    }
};

解法二：计算出两个链表的长度，找出多余的部分。将长链表指针移动到和较短链表对应的位置。headA和headB同时向后移动，如果headA===headB,就返回当前节点。

 var getNodeLength = function(head){
    let length = 0;
    while(head){
        length++;
        head = head.next;
    }
    return length;
}
var removeHeadNode = function(head,length){
    length = Math.abs(length);
    while(head&&length){
        head = head.next;
        length--;
    }
    return head;
}
var getIntersectionNode = function(headA, headB) {
  let lengthA = getNodeLength(headA);
  let lengthB = getNodeLength(headB);
  let otherLength = lengthA - lengthB;
  if(otherLength < 0){
      headB = removeHeadNode(headB,otherLength)
  }else{
      headA = removeHeadNode(headA,otherLength)
  }
  while(headA&&headB){
      if(headA===headB){
          return headA;
      }else{
          headA = headA.next;
          headB = headB.next;
      }
  }
  return null;
};

（5）链表划分，链表分隔86

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
解法：利用两个临时头结点，less_head和more_head，分别记录小于和大于等于x的链表，然后用less_ptr和more_ptr遍历，最后拼接起来并把more_ptr置空，再返回less_head.next。

var partition = function(head, x) {
  let less_head = new ListNode(null);
  let more_head = new ListNode(null);
  let less_ptr = less_head;
  let more_ptr = more_head;
  while(head){
      if(head.val < x){
          less_ptr.next = head;
          less_ptr = head;
      }else{
          more_ptr.next = head;
          more_ptr = head;
      }
      head = head.next;
  }
  less_ptr.next = more_head.next;
  more_ptr.next = null;
  return less_head.next;
};

(6）复杂链表实现深拷贝

（7）2个排序列表的合并

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：创建一个新的头结点，比较两个链表相同长度的部分，再判断head1和head2是否有剩余，如果有，拼接在新链表之后即可。

var mergeTwoLists = function(list1, list2) {
    let newHead = new ListNode(null);
    let new_ptr = newHead;
    while(list1&&list2){
        if(list1.val <= list2.val){
            new_ptr.next = list1;
            new_ptr = new_ptr.next;
            list1 = list1.next;
        }else{
            new_ptr.next = list2;
            new_ptr = new_ptr.next;
            list2 = list2.next;
        }
    }
     if(list1){
        new_ptr.next = list1;
    }
    if(list2){
        new_ptr.next = list2;
    }
    return newHead.next;
};

（8）多个有序链表的排序

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解法一:
将k*n个链表的节点放到一个数组中，对这个数组中的val进行排序，排序之后连接起来，返回合并之后的头结点。

var mergeKLists = function(lists) {
    let node_vec = [];
    let ptr = lists[0]
    for(var i=0;i<lists.length;i++){
         ptr = lists[i];
         while(ptr){
            node_vec.push(ptr);
            ptr = ptr.next;
        }
    }
    node_vec.sort((a,b)=>{return a.val-b.val})
    for(var i=1;i<node_vec.length;i++){
        node_vec[i-1].next = node_vec[i]
    }
    node_vec[node_vec.length-1]!=undefined?node_vec[node_vec.length-1].next=null:node_vec[0]=null
    return node_vec[0]
};

解法二：对k个链表进行分治，两两进行合并。也就是将lists分为两个数组，分别递归合并，最后将两个数组再合并（！！！注意js除法除出来是浮点数，要向下或者向上取整）

 var mergeTwoLists = function(list1, list2) {
    let newHead = new ListNode(null);
    let new_ptr = newHead;
    while(list1&&list2){
        if(list1.val <= list2.val){
            new_ptr.next = list1;
            new_ptr = new_ptr.next;
            list1 = list1.next;
        }else{
            new_ptr.next = list2;
            new_ptr = new_ptr.next;
            list2 = list2.next;
        }
    }
    if(list1){
        new_ptr.next = list1;
    }
    if(list2){
        new_ptr.next = list2;
    }
    return newHead.next;
};
var mergeKLists = function(lists) {
    if(lists.length === 0){
        return null;
    }
    if(lists.length === 1){
        return lists[0];
    }
    if(lists.length === 2){
        return mergeTwoLists(lists[0],lists[1]);
    }
    let mid = Math.floor(lists.length/2);
    let list1 = [];
    let list2 = [];
    for(let i = 0;i<mid;i++){
        list1.push(lists[i])
    }
    for(let i = mid;i<lists.length;i++){
        list2.push(lists[i])
    }
    let ptr1 = mergeKLists(list1);
    let ptr2 = mergeKLists(list2);
    return mergeTwoLists(ptr1,ptr2)
};