题型一：

有序数组的平方

image.png
思路：找到非负数与负数的临界区，平方后前半部分为降序，后半部分为升序。从分界区左右各放置一个指针，向左与向右遍历，依次比较放入新的数组中。某一部分遍历完则将另一部分剩余遍历后放入数组中。

  1. var mid;
  2.     for(let i = 0;i<nums.length;i++){
  3.       if(nums[i]<=0) mid = i;
  4.     else break;
  5.   }//找出临界值
  6. var left = mid;
  7. var right = mid+1;
  8. var num = new Array();
  9.     while(left>=0||right<nums.length){
  10.       if(left<0){
  11.         num.push(nums[right]*nums[right]);
  12.       right++;
  13.     }
  14.     else if(right == nums.length){
  15.         num.push(nums[left]*nums[left]);
  16.       left--;
  17.     }
  18.     else if((nums[left]*nums[left])<nums[right]*nums[right]){
  19.         num.push(nums[left]*nums[left]);
  20.       left--;
  21.     }
  22.     else {
  23.         num.push(nums[right]*nums[right]);
  24.       right++;
  25.     }
  26.   }
  27. return num;

题型二：

环形链表

image.png
image.png
思路：快慢指针，一个每次走一步，另一个每次走两步。倘若两个指针相等了，则说明链表有闭环。

  1. var hasCycle = function(head) {
  2.     let slow = head;
  3.     let fast = head;
  4.     while(fast && fast.next) {
  5.         slow = slow.next;
  6.         fast = fast.next.next;
  7.         if(slow === fast) {
  8.             return true;
  9.         }
  10.     }
  11.     return false;
  12. };

题型三：

链表的中间结点

image.png
思路：快慢指针，一个每次走一步，另一个每次走两步。快指针到达终点时，慢指针到达的则是中间位置。

  1. var fast = head;
  2. var slow = head;
  3.         while(fast&&fast.next){
  4.             slow = slow.next;
  5.             fast = fast.next.next;
  6.         }
  7.     return slow;

题型四：

删除链表的倒数第 N 个结点

image.png
思路：慢指针指向哑结点，快指针指向头结点。快指针先走N步，然后快慢同时行动。当快指针走到null时，慢指针所在的位置即为倒数第N个结点的前驱结点。然后返回初始哑结点的前驱结点即为初始结点。

  1.          var fast = head;
  2.     var dummy = new ListNode(0);
  3.     dummy.next = head;
  4.     slow = dummy;
  5.     for(let i = 0;i<n;i++){
  6.         fast = fast.next;
  7.     }
  8.     while(fast){
  9.         fast = fast.next;
  10.         slow = slow.next;
  11.     }
  12.     slow.next = slow.next.next;
  13.     var out = dummy.next;
  14.     return out;

题型五：

合并两个有序数组

image.png
思路：逆向双指针
与双指针不同的是，利用nums1后面的多余空间来填补，避免覆盖nums1数据所需要创建一个新的数组。
空间复杂度降低了。

  1. var merge = function(nums1, m, nums2, n) {
  2.     let p1 = m-1;
  3.     let p2 = n-1;
  4.     let need = m + n -1;
  5.     var temp;
  6.     while(p1>=0||p2>=0){
  7.         if(p1 ==-1){
  8.             temp = nums2[p2--];
  9.         }
  10.         else if(p2 ==-1){
  11.             temp = nums1[p1--]; 
  12.         }
  13.         else if(nums1[p1]>nums2[p2]){
  14.             temp = nums1[p1--];
  15.         }
  16.         else temp = nums2[p2--];
  17.         nums1[need--] = temp;
  18.     } 
  19.     return nums1; 
  20. };