反转链表

反转链表
两两交换
反转链表2

25. K 个一组翻转链表

  1. var reverse=function(head,tail){
  2.     let pre=tail.next,cur=head;
  3.     //翻转，巩固反转链表这道题
  4.     while(pre!==tail){
  5.         let next=cur.next;
  6.         cur.next=pre;
  7.         pre=cur;
  8.         cur=next;
  9.     }
  10.     return [tail,head]
  11. }
  12. var reverseKGroup = function(head, k) {
  13.     let hair=new ListNode(null,head)
  14.     let pre=hair;
  15.     while(head){
  16.         let tail=pre;
  17.         //看剩余是否还有k个，拿到tail
  18.         for(let i =0;i<k;i++){
  19.            tail=tail.next;
  20.            if(!tail) return hair.next;
  21.         }
  22.         [head,tail]= reverse(head,tail)
  23.         // 把子链表重新接回原链表
  24.         pre.next=head;
  25.         pre=tail;
  26.         head=tail.next;
  28.     }
  29.     return hair.next;
  30. };

回文链表

  1. //方法一 把原始链表反转存入一条新的链表，然后比较这两条链表是否相同
  2. var isPalindrome = function (head) {
  3.   let pre = null,cur = head;
  4.   while (cur) {
  5.     let newNode = new ListNode(cur.val, pre);
  6.     pre = newNode;
  7.     cur = cur.next;
  8.   }
  9.   cur = head;
  10.   while (pre) {
  11.     if (pre.val !== cur.val) {
  12.       return false;
  13.     }
  14.     pre = pre.next;
  15.     cur = cur.next;
  16.   }
  17.   return true;
  18. };
  19. //方法二 利用后序遍历递归比较
  20. var isPalindrome = function (head) {
  21.  let left = head;
  22.   function tranverse(node) {
  23.     if (node === null) return true;
  24.     let res=tranverse(node.next);
  25.     res = res && (node.val === left.val)
  26.     left = left.next;
  27.     return res;
  28.   }
  29.   return tranverse(head);
  30. };
  31. //方法三：快慢指针加反转链表 O(N) O(1)
  32. //Your runtime beats 98.5 % of javascript submissions
  33. //Your memory usage beats 96.07 % of javascript submissions (55.2 MB)
  34. var isPalindrome = function (head) {
  35.   let slow = head,
  36.     pre = null,
  37.     fast = head;
  38.   while (fast && fast.next) {
  39.     fast = fast.next.next;//fast需要提前赋值，防止反转链表后找不到
  40.       // 反转前半部分链表
  41.     let next = slow.next;
  42.     slow.next = pre;
  43.     pre = slow;
  44.     slow = next;
  45.   }
  46.   // 如果是奇数节点慢指针还得往后走一个
  47.   if (fast) {
  48.     slow = slow.next;
  49.   }
  50.   while (slow) {
  51.     if (slow.val !== pre.val) return false;
  52.     slow = slow.next;
  53.     pre = pre.next;
  54.   }
  55.   return true;
  56. };

双指针

203. 移除链表元素

简单题，双指针

  1. var removeElements = function(head, val) {
  2.     let result=new ListNode(null,head);//虚拟节点，以防第一个节点被删除
  3.     let pre=result,cur=head;
  4.     while(cur){
  5.        const next=cur.next;
  6.        if(cur.val==val){
  7.            pre.next=next;
  8.        }else{
  9.            pre=cur
  10.        }
  11.        cur=next;
  12.     }
  13.     return result.next;
  14. };

876. 链表的中间结点

使用快慢双指针

  1.  var middleNode = function(head) {
  2.     let fast=slow=head
  3.     while(fast!==null&&fast.next!==null){
  4.         slow=slow.next 
  5.         fast=fast.next.next 
  6.     }
  7.     return slow
  8. };

237. 删除链表中的节点

用覆盖节点值的方式 代替 直接删除原节点。

  1. var deleteNode = function (node) {
  2.     let cur = node;
  3.     while (cur && cur.next) {
  4.         cur.val = cur.next.val;
  5.         if (!cur.next.next) cur.next = null;
  6.         cur = cur.next;
  7.     }
  8. };