[链表]

[Linjiayu6]

1 - 面试题24. 反转链表

同206. 反转链表

# 迭代
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None: return None
        if head.next is None: return head

        slow, fast = None, head
        while fast:
            tmp = fast.next
            fast.next = slow
            slow = fast
            fast = tmp
        return slow

# 递归
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None: return None
        if head.next is None: return head

        def swap (slow, fast):
            if fast is None: return slow
            tmp = fast.next
            fast.next = slow
            slow = fast
            fast = tmp
            return swap(slow, fast)
        slow, fast = None, head
        return swap(slow, fast)

[Linjiayu6]

2 - 21. 合并两个有序链表 🔥

// 迭代
var mergeTwoLists = function(l1, l2) {
    var result = new ListNode(null)
    var r = result
    while (l1 || l2) {
        if (!l1 && l2) {
            r.next = l2
            return result.next
        }
        if (l1 && !l2) {
            r.next = l1
            return result.next
        }

        if (l1.val < l2.val) {
            r.next = new ListNode(l1.val)
            l1 = l1.next
            r = r.next
        } else {
            r.next = new ListNode(l2.val)
            l2 = l2.next
            r = r.next
        }
    }

    return result.next
};

递归题解

// 递归
// l1.val < l2.val, 改变指向到 l1.next = = l2, 再递归再处理
var mergeTwoLists = function(l1, l2) {
    if (!l1 && !l2) return l1
    if (!l1 && l2) return l2
    if (l1 && !l2) return l1
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    }
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
};

[Linjiayu6]

3 - 141. 环形链表

map 方式

var hasCycle = function(head) {
    var map = new Map()
    while (head) {
        if (map.get(head) === head) {
            return true
        }
        map.set(head, head)
        head = head.next
    }
    return false
};

快慢指针

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    /**
     * 快慢指针
     * 快指针2倍 fast = head.next.next, slow = head
     * 快慢重合则为true
     * 如果快指针越界 或 为Null return false
     */

    if (!head || !head.next || !head.next.next) return false
    var fast = head.next.next, slow = head
    while (fast && slow) {
        if (fast === slow) return true
        slow = slow.next
        if (!fast.next || !fast.next.next) {
            return false
        }
        fast = fast.next.next
    }
    return false
};

[Linjiayu6]

4 - 206. 反转链表

迭代

var reverseList = function(head) {
    /**
     * 1 -> 2 -> 3 -> null
     * start = null
     * tempHead = head.next
     * head.next = start
     * start = head
     * head = tempHead
     * null <-1(start) (head)2->3
     * 
     * 直到head null, 则返回 start
     */
    if (!head) return null
    var start = null
    while (head) {
        var tempHead = head.next
        head.next = start
        start = head
        head = tempHead
    }
    return start
};

递归

var reverseList = function(head) {
    var start = null
    function traverse(start, head) {
        if (!head) return start // 结束条件
        var _newHead = head.next
        head.next = start
        // start = head
        // head = _newHead
        // return traverse(start, head)
        return traverse(head, _newHead)
    }

    return traverse(start, head)
};

[Linjiayu6]

5 - 876. 链表的中间结点

计算类型

var middleNode = function(head) {
    if (!head) return head
    var len = 0, h = head
    while (h) {
        h = h.next
        len += 1
    }
    // 这里half值总错
    var half = Math.floor(len / 2)
    for (let i = 0; i < half; i++) {
        head = head.next
    }
    return head
};

快慢指针 🔥 🔥🔥🔥🔥 总错

var middleNode = function(head) {
  if (!head || head && !head.next) return head 
  var slow = head, fast = head.next.next // slow 走一步 fast 走两步
  while (fast) {
    // 针对奇数情况
    if (!fast.next) return slow.next // 例如 [1, 2, 3] slow = 1, fast = 3 fast.next=null, 则返回的是 slow.next => 2
    fast = fast.next.next // 继续往下走
    slow = slow.next
  }

  // 针对偶数情况
  return slow.next // [1, 2, 3, 4] slow = 2, fast = null 返回结果是 slow.next
};

[Linjiayu6]

6 - 19. 删除链表的倒数第N个节点

1 - 找位置 删除

var removeNthFromEnd = function(head, n) {
  var _len = 0, h = head
  while (h) {
    h = h.next
    _len += 1
  }

  n = n > _len ? n % _len : n
  var pos = _len - n
  if (pos === 0) return head.next // 第一个删除
  var i = 1, r = head
  while (i < pos) {
    r = r.next
    i += 1
  }
  r.next = r.next.next ? r.next.next : null
  return head
};

2 - 快慢指针 🔥🔥🔥🔥🔥

var removeNthFromEnd = function(head, n) {
  var fast = head, slow = head
  var i = 0
  // 先找 fast 位置
  while (i < n) {
    fast = fast.next 
    if (!fast) fast = head // 当fast 越界, 则重新轮回
    i += 1
  }
  // 此时他们相同了, 则直接返回下一个结点
  if (fast === slow) return head.next

 // 当fast的一下是null, 则暂停slow的遍历
  while (fast.next) {
    slow = slow.next
    fast = fast.next
  }

  slow.next = slow.next.next ? slow.next.next : null
  return head
};

3 - 快慢指针 + 新增个头结点🔥🔥🔥🔥🔥

var removeNthFromEnd = function(head, n) {
  if (!head) return head
  var _newHead = new ListNode(null)
  _newHead.next = head

  var slow = _newHead, fast = _newHead
  while (n --) {
    if (!fast.next) {
      fast = head
      continue
    }
    fast = fast.next
  }

  while (fast && fast.next) {
    fast = fast.next
    slow = slow.next
  }

  slow.next = slow.next.next
  return _newHead.next
};

[Linjiayu6]

7 - 160. 相交链表

标记方法🔥

var getIntersectionNode = function(headA, headB) {
    // A遍历一遍, 整个标记, 遍历B的时候有该标记就是true
    while (headA) {
        headA.flag = true
        headA = headA.next
    }

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

map 方法

var getIntersectionNode = function(headA, headB) {
    /**
     * 先遍历A, 放入map中, 这里存的是地址, 不是某个值
     * 再遍历B, 检查map内容, 如果B用尽, 则return false
     */
    if (!headA || !headB) return null
    var map = new Map()
    while (headA) {
        map.set(headA, headA) // 注意 🔥 存的是地址
        headA = headA.next
    }

    while (headB) {
        if (map.get(headB) === headB) return headB
        headB = headB.next
    }

    return null
};

[Linjiayu6]

单链表

class Node {
  constructor (data, next = null) {
    this.data = data
    this.next = next
  }
}

class LinkedList {
  constructor () {
    this.head = null
    this.length = 0
  }
  // 头插入
  appendHead (data) {
    var newNode = new Node(data)
    if (this.head === null) {
      this.head = newNode
    } else {
      newNode.next = this.head
      this.head = newNode
    }
    this.length += 1
  }

  // 尾插入
  append(data) {
    var newNode = new Node(data)
    if (this.head === null) {
      this.head = newNode
    } else {
      var temp = this.head
      while (temp.next) {
        temp = temp.next
      }
      temp.next = newNode
    }
    this.length += 1
  }

  // 查找
  search(data) {
    var temp = this.head
    while (temp) {
      if (temp.data === data) {
        return true
      }
      temp = temp.next
    }
    return false
  }

  // 在某个位置插入 pos从0开始
  insert(pos, data) {
    if (pos === 0) {
      this.appendHead(data)
      return
    }

    if (pos > this.length) {
      this.append(data)
      return
    }

    var i = 0
    var temp = this.head
    while (i < pos - 1) {
      temp = temp.next
      i += 1
    }
    var _newnode = new Node(data)
    _newnode.next = temp.next
    temp.next = _newnode

    this.length += 1
  }

  delete (data) {
    if (this.head === null) return // 没有头结点
    if (this.head.data === data) { // 头结点为匹配值
      this.head = this.head.next
      this.length -= 1
      return true
    }

    var temp = this.head
    while (temp.next) {
      if (temp.next.data === data) {
        temp.next = temp.next.next
        this.length -= 1
        return true
      }
      temp = temp.next
    }

    return false
  }
}

var list = new LinkedList()
list.append(1)
list.append(2)
list.appendHead(-1)
list.appendHead(0)

list.insert(0, 666)
list.insert(10, 666)
list.insert(3, 666)
console.log(list)
list.delete(666)
console.log(list)
list.delete(666)
console.log(list)
list.delete(666)
console.log(list)