双指针

lc160. 求相交链表的第一个相交节点简单hot

题目描述

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

思路一：标志法

给链表的每个节点添加一个标志flag

但是链表需要保持原有的结构，所以这种方法不可取（虽然能过）

时间复杂度O(n)

空间复杂度O(n)

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }

    while(headB) {
        if(headB.flag) return headB
        headB = headB.next
    }
    return null
};

可见空间复杂度O(n)只击败可怜的5%

双指针 来清除高度差

我们知道这两个链表有可能是不一样的长度的，我们需要清楚高度差，然后让两个链表同时运动的节点相遇然后来找到相交的点

来个图助助兴

• 首先先同步遍历A B链表pA和pB直到遍历完一个短链

• pB先遍历完 然后pB指针指到A链表，然后进行下一次遍历，当pA遍历完pA指向B链表

• 然后一直循环直到pB和pA指向同一个节点，即为相交的第一个节点

• 如果没有相交那就返回null

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let pA = headA
    let pB = headB
    while(pA !== pB){
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
};

时间复杂度O(n)

空间复杂度O(1)

lc203. 移除链表元素简单

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6

输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1

输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7

输出：[]

var removeElements = function(head, val) {
  let dummyHead = new ListNode(null)
  dummyHead.next = head
  let pre = dummyHead
  let cur = head

  while(cur) {
    cur.val === val ? pre.next = cur.next : pre = cur
    cur = cur.next
  }
  return dummyHead.next
};

时间复杂度:O(n)

空间复杂度:O(1)

lc83. 删除排序链表的重复元素简单hot

题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]

输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]

输出：[1,2,3]

思路同移除链表元素一样

var deleteDuplicates = function(head) {
  let duummyHead = new ListNode(null)
  duummyHead.next = head
  let pre = duummyHead
  let cur = head
  while(cur) {
    cur.val === pre.val ? pre.next = cur.next : pre = cur
    cur = cur.next
  }

  return duummyHead.next
};

时间复杂度:O(n)

空间复杂度:O(1)

lc82. 删除排序链表的重复元素 II中等hot

题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]

输出：[2,3]

var deleteDuplicates = function(head) {
    // 处理链表只有0或1个节点的情况
    if(!head||!head.next){
        return head
    }
    // 设置虚拟头节点
    let dummy = new ListNode(null)
    dummy.next = head
    // 设置当前节点
    let cur = dummy

    while (cur.next && cur.next.next){
        if(cur.next.val === cur.next.next.val){
            // 保存重复节点的值
            let val =cur.next.val
            // 反复判断是否还有相等的节点
            while(cur.next && cur.next.val === val){
              cur.next = cur.next.next
            }
        }else{
            cur = cur.next
        }
    }
    // 返回最终结果，也就是链表的起始的节点
    return dummy.next
};

时间复杂度:O(n)

空间复杂度:O(1)

lc147. 对链表进行插入排序中等

题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。

每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3

输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0

输出: -1->0->3->4->5

思路

就是设置一个last和first节点，first节点都在last节点之后，首先先让first节点和last节点进行比较，如果大于last节点，那么就顺序不改变，如果小于last节点的话，就从头开始遍历链表进行插入

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
  if(!head) return head

  let last = head
  let first = head.next
  let dummyHead = new ListNode(null)
  dummyHead.next = head
  while(first) {
    if(last.val <= first.val) {
      last = last.next
    } else {
      let cur = dummyHead
      while(cur.next.val <= first.val) {
        cur = cur.next
      }
      last.next = first.next
      first.next = cur.next
      cur.next = first
    }
    first = last.next
  }
  return dummyHead.next
};

• 时间复杂度：O(n)，对于链表而言，插入元素时只要更新相邻节点的指针即可，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)，需要额外的常数大小的辅助空间。

lc328. 奇偶链表中等

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 

输出: 2->3->6->7->1->5->4->NULL

var oddEvenList = function(head) {
    if(head === null || head.next === null || head.next.next === null){
        return head
    }
    let a = head       // 存放奇数节点
    let b = head.next  // 存放偶数节点
    const node = head.next   // 记录b链表的头节点
    while(b && b.next){
        a.next = b.next
        a = a.next
        b.next = a.next
        b = b.next
    }
    a.next = node
    return head
};

时间复杂度:O(n)

空间复杂度:O(1)