反转链表

反转链表LeetCode206
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
输入：head = [] 输出：[]

总体思路就是将下一个节点的next指向上一个节点
可以使用两种方法来实现：循环和递归

  1. // 使用while循环方式
  2. var reverseList = function(head) {
  3.   if (head === null || head.next === null) {
  4.     return head;
  5.   }
  7.   let p = head;
  8.   let q = new ListNode(head.val);
  10.   while(p.next !== null) {
  11.     const k = new ListNode(p.next.val);
  12.     k.next = q;
  13.     q = k
  14.     p = p.next
  15.   }
  17.   return q;
  18. };
  19. // 使用递归方式
  20. var reverseList = function(head) {
  21.   if (head === null || head.next === null) {
  22.     return head;
  23.   }
  24.   const node = new ListNode();
  25.   let temp = node;
  26.   var dfs = function(p) {
  27.     if (p.next !== null) {
  29.       dfs(p.next);
  30.     }
  31.     temp.next = new ListNode(p.val);
  32.     temp = temp.next;
  33.   }
  34.   dfs(head);
  36.   return node.next;
  37. };

反转链表 II

反转链表II LeetCode92
题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。链表节点数、left、right均大于1
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
输入：head = [5], left = 1, right = 1 输出：[5]

这个是反转链表的升级版，将指定[left, right]区域进行反转，假设链表长度为n，可将链表分为3部分：[1, left)、[left, right], (right, n]
[1, left)这部分正常遍历，[left, right]遍历时将下一个node的next指向上一个节点，(right, n]可以不用遍历，直接让上一部分的指针指向right位置的节点即可
这儿也可以使用两种方法：循环和递归

  • revertHeader指向部分反转链表[left, right]的头部
  • revertTail指向部分反转链表[left, right]的尾部

  • residualHeaderTail指向最开始遍历部分链表[1, left)的尾部 ```javascript // 使用while循环 var reverseBetween = function(head, left, right) { let revertHeader = null; let revertTail = null; let residualHeaderTail = null;

    let p = head; let level = 1;

    while (p !== null) { // [1, left)部分链表遍历 if (level === left - 1) {

    1. residualHeaderTail = p;

    } // [left, right]部分链表赋初始值 if (level === left) {

    1. revertHeader = new ListNode(p.val);
    2. revertTail = revertHeader;

    } // [left, right]部分链表反转 // revertHeader始终指向反转链表的头部 if (level > left && level <= right) {

    1. const q = new ListNode(p.val);
    2. q.next = revertHeader;
    3. revertHeader = q;

    } // (right, n]部分链表直接在反转链表尾部revertTail添加上即可 if (level > right) {

    1. revertTail.next = p;
    2. break;

    } level ++; p = p.next; } // 存在两者情况 // 1、存在left = 1的情况，即链表从头开始反转， // 此时整个反转链表的头部就是revertHeader // 2、链表不是从头开始反转的，left > 1, 此时residualHeaderTail有值 // 进行拼接即可，整个反转链表的头部为head if (residualHeaderTail) { residualHeaderTail.next = revertHeader; revertHeader = head; }

    return revertHeader;

};

  1. 使用递归方式如下，先递归链表，递归到不需要递归的部分(right, n]，停止递归
  3. - revertHeader指向部分反转链表[left, right]的头部
  4. - revertTail指向部分反转链表[left, right]的尾部
  5. - residualTailHeader指向最后不用遍历的部分链表(right, n]的头部
  6. - flag是一个标志符
  7. ```javascript
  8. // 使用递归
  9. var reverseBetween = function(head, left, right) {
  10.   let revertHeader = null;
  11.   let revertTail = null;
  12.   let residualTailHeader = null;
  13.   let flag = false;
  15.   const traverse = (node, level = 1) => {
  16.     if (node === null) {
  17.       return
  18.     }
  19.     // 递归到right位置后停止递归
  20.     if (level <= right) {
  21.       traverse(node.next, level + 1);
  22.     } else if (level === right + 1) {
  23.       // residualTailHeader指向(right, n]的头部
  24.       residualTailHeader = node;
  25.     }
  26.     // [left, right]部分链表赋初始值
  27.     if (level === right) {
  28.       revertHeader = new ListNode(node.val)
  29.       revertTail = revertHeader;
  30.     } else if (level >= left && level < right) {
  31.       // [left, right]部分链表反转
  32.       // revertTail始终指向部分反转链表的尾部
  33.       revertTail.next = new ListNode(node.val);
  34.       revertTail = revertTail.next
  35.     } else if (level < left && !flag) {
  36.       // 将revertHeader和[1, left)部分链表链接起来
  37.       // 递归过程中只用执行一次
  38.       node.next = revertHeader;
  39.       revertHeader = head;
  40.       flag = true;
  41.     }
  42.   }
  44.   traverse(head);
  45.   revertTail.next = residualTailHeader
  47.   return revertHeader;
  49. };

环形链表II

环形链表II LeetCode142
题目: 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

一种是暴力遍历，把遍历到到的节点都存在Map结构里，继续遍历下去，在Map结构中找到第一个相同的节点就是入环点
一种是根据数学公式计算出来的：设置快慢指针fast、slow，slow以每次一个节点的速度遍历，fast以每次2个节点的速度遍历，slow、fast同时出发，当slow与fast相遇后，设置一个新指针p从头节点以一个节点的速度遍历，p与slow相遇的地方就是入环点
计算原理如下
如果有环，快慢指针必定会相遇，且慢指针会在入环的一圈之内与快指针相遇
假设slow的速度为1，fast的速度为2，环的长度为L，则slow、fast指针相距的最大距离为L-1，由于fast的速度比slow快1个节点，所以每次移动的时候就会追上一个节点，那么fast指针最多移动(L-1)*1次即可追上，此时slow指针还没有走完一圈，所以slow、fast一定会在slow入环的第一圈就会相遇，所以可以得到下面公式
链表 - 图1
链表 - 图2

所以从头节点出发的指针p与从slow、fast相遇点继续出发的slow指针同时出发，一定会在入环点处相遇

  1. // flag用来表示快慢指针相遇了，新指针可以出发了
  2. var detectCycle = function(head) {
  3.   let slow = head;
  4.   let fast = head;
  5.   let p = head;
  6.   let flag = false;
  8.   while(fast !== null) {
  9.     slow = slow.next;
  10.     if (fast.next) {
  11.       fast = fast.next.next
  12.     } else {
  13.       return null;
  14.     }
  15.     if (slow === fast) {
  16.       flag = true;
  17.     }
  18.     if (p === slow) {
  19.       return p;
  20.     }
  21.     if (flag) {
  22.       p = p.next;
  23.     }
  24.   }
  25.   return null;
  26. };

相交链表

相交链表LeetCode160
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。整个链式结构中不存在环。

这个和环形链表找入环点一样，可以暴力枚举，也可以简单遍历
假设链表相交，A，B链表的长度分别是m和n，m > n，p，q指针分别从A，B链表的头节点出发，p先走m-n步，然后q出发，则在相交点是p与q相等
怎么先让p指针先走m-n步呢，p，q分别遍历到链表尾部，q指针到达B链表尾部后指向A链表头部，p指针到达A链表尾部后指向B链表头部，此时q指针已经走了m-n步了，继续遍历，p与q相等则为相交点

  1. var getIntersectionNode = function(headA, headB) {
  2.   let p = headA, q = headB;
  3.   while(p !== null || q !== null) {
  4.     if (p === q) {
  5.       break;
  6.     }
  7.     if (p!== null) {
  8.       p = p.next;
  9.     } else {
  10.       p = headB;
  11.     }
  12.     if (q!== null) {
  13.       q = q.next;
  14.     } else {
  15.       q = headA;
  16.     }
  17.   }
  18.   return p;
  19. };

旋转链表

旋转链表LeetCode61
题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
输入：head = [0,1,2], k = 4 输出：[2,0,1]

可以简化一下这个题目，链表的长度为m，当k = m时，链表与原链表是一致的没有移动，可以对k取余，v = k%m，且v < m
将链表的尾部指针指向头节点形成一个环，将链表向右移动v个位置，即将链表后v个节点前置，即头节点向后遍历m-v个节点后断开环，即为移动后的新链表

  1. var rotateRight = function(head, k) {
  2.   if (head === null || k === 0) return head;
  4.   let p = head, length = 1;
  5.   let result = null;
  6.   while(p.next!== null) {
  7.     p = p.next;
  8.     length++;
  9.   }
  10.   // 形成环
  11.   p.next = head;
  12.   // 计算头节点向后遍历多少次后断开环
  13.   let value = length - (k - Math.floor(k/length) * length);
  14.   while(value > 1) {
  15.     head = head.next;
  16.     value--
  17.   }
  18.   result = head.next;
  19.   head.next = null;
  20.   return result;
  21. };

合并两个有序链表

合并两个有序链表LeetCode88
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = [] 输出：[]
输入：l1 = [], l2 = [0] 输出：[0]

使用双指针指向两个链表的头部，然后比较当前数字大小，为了节省空间，新链表的每一项可以直接使用原来链表的项

  1. var mergeTwoLists = function(list1, list2) {
  2.   let result = new ListNode();
  3.   let p = list1, q = list2, cur = result;
  4.   while (p !== null && q !== null) {
  5.     if (p.val > q.val) {
  6.       cur.next = q;
  7.       q = q.next;
  8.     } else {
  9.       cur.next = p;
  10.       p = p.next;
  11.     }
  12.     cur = cur.next;
  13.   }
  14.   cur.next = p === null ? q : p;
  15.   return result.next;
  16. };