[数据结构与算法]链表练习记录

链表练习记录

一、首先是找链表中点（快慢指针）

function findCenter(head){
    let fast = head,slow = head;
    while(fast||fast.next!==null){
          slow = slow.next
          fast = fast.next.next
     }
     if(fast!==null){
        slow =slow.next
}
  return slow
}

二、接着是反转链表

function reverse(head){
    let arr= []
    let node = head
    while(head){
      arr.push(head.val)
      head = head.next
    }
     let res = node//现在node已经在原链表的末端
     while(node){
         node.val= arr.pop()
         node = node.next
   }
   return res
}

或者

function reverse(head){
    if(head==null||head.next==null)return head
    let res = reverse(head.next)//现在res在原链表末端，因为使用了递归
    head.next.next=head
    head.next =null
    return res
}

三、合并有序链表

function merge(l1,l2){
  let dummy = new listNode(0)
  let prev = dummy
  while(l1&&l2){
       if(l1.val<l2.val){
          prev.next = l1
          l1 = l1.next
        }else{
        prev.next = l2
        l2 = l2.next
       }
       prev= prev.next
  }
    if (l1) prev.next = l1;
    if (l2) prev.next = l2;
    return dummy.next
}

四、给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
此题借助上面的方法可以做出：

var sortList = function (head) {
    if (!head || !head.next)  return head;
    let slow = head, fast = head;
    let preSlow = null;
    while (fast && fast.next) {//这里先找到中点之前的那个节点，成为preSlow
        preSlow = slow;
        slow = slow.next;//中点
        fast = fast.next.next;
    }
    preSlow.next = null;
    const l = sortList(head);//分左右两边分别进行递归，归并算法，分解成最小单位
    const r = sortList(slow);
    return merge(l, r);
};
//合并有序链表
function merge(l1, l2) {
    const dummy = new ListNode(0);
    let prev = dummy;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    if (l1) prev.next = l1;
    if (l2) prev.next = l2;
    return dummy.next;
}

五、回文链表
同样可以借助以上方法，找到中点，然后找到末端，将中点到末端的这一部分进行反转，然后与前面一段相比较

var isPalindrome = function(head) {
        let right = reverse(findCenter(head))
        let left= head
        //开始比较
        while(right){
            if(left.val!==right.val){
                return false
            }
            left = left.next
            right = right.next
        }
        return true
};

//找中点
function findCenter(head){
    let slow = head,fast = head;
    while(fast&&fast.next!==null){
        slow = slow.next
        fast = fast.next.next
    }
    if(fast!==null){
        slow = slow.next
    }
    return slow
}
//反转链表
function reverse(head){
    let arr = []
    let node = head
    while(head){
        arr.push(head.val)
        head = head.next
    }
    let res = node 
    while(node){
        node.val = arr.pop()
        node = node.next
    }
    return res
}

六、相交链表，判断两个链表是否有相交之点
可以通过快慢指针，将两个链表形成一个环，不断循环，然后判断是否会相遇即可
此题解题思路一样可以用于牛客第141题环形链表，快慢指针是否会相遇来判断环形是否成立。

var getIntersectionNode = function(headA, headB) {
    let h1 = headA
    let h2 = headB
    while(h1!==h2){
          if(h1==null){
              h1 = headB
          }else{
              h1 = h1.next
          }
          if(h2==null){
              h2 = headA
          }else{
              h2 = h2.next
          }
    }
    return h1
};

七、给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序

var reverseKGroup = function(head, k) {
 let a = head, b = head;
    for (let i = 0; i < k; i++) {
        if (b == null) return head;
        b = b.next;
    }
    const newHead = reverse(a, b);
    a.next = reverseKGroup(b, k);
    return newHead;
};
function reverse(a, b) {
    let prev = null, cur = a, nxt = a;
    while (cur != b) {
        nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
};