链表

反转链表 (opens new window)

反转一个单链表。

function reverseList(head: ListNode | null): ListNode | null {
  let pre: ListNode | null = null
  let current = head
  while (current) {
    const next = current.next
    current.next = pre
    pre = current
    current = next
  }

  return pre
}

复杂链表的复制 (opens new window)

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

class Node {
  val: number
  next: Node | null = null
  random: Node | null = null
  
  constructor(val: number) {
    this.val = val
  }
}

function copyRandomList(head: Node | null): Node | null {
  if(!head) return null
  
  // 准备工作
  const newHead = new Node(head.val)
	let node = head
  let newNode = newHead
  const hashMap = new Map<Node, Node>([
    [node, newNode] // 初始化
  ])
  
  while(node.next) {
    newNode.next = new Node(node.next.val)
    node = node.next
    newNode = newNode.next
    hashMap.set(node, newNode)
  }
  
  // 复制完毕之后，指针还原，进行 random 复制
  node = head
  newNode = newHead
  
  while(node) {
    newNode.random = hashMap.get(node.random)
    node = node.next
    newNode = newNode.next
  }
  
  return newHead
}

合并两个有序链表 (opens new window)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if(!l1) return l2
  else if(!l2) return l1
  
  if(l1.val < l2.val) {
    l1.next = mergeTwoList(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoList(l1, l2.next)
    return l2
  }
}

环形链表 (opens new window)

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

function hasCycle(head: ListNode | null): boolean {
  while(head) {
    if(head.flag) return true
    head.flag = true
    head = head.next
  }
  return false
}

环形链表II (opens new window)

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

function hasCycle(head: ListNode | null): ListNode | null {
  // 快慢指针都从头节点出发
  let slow = head
  let fast = head 
  
  while(fast) { // 如果空链表就直接退出去返回 null
    if(fast.next === null) return null // 如果快指针没有下一个节点，说明无环
    slow = slow.next
    fast = fast.next.next
    if(slow === fast) { // 首次相遇
      fast = head // 快指针回到头节点
      while(true) {
        if(slow === fast) { // 此时相遇，慢指针到达之前第一次相遇时快指针所在位置
          return slow
        }
        fast = fast.next // 首次相遇之后，快指针不再需要一次走两步
        slow = slow.next
      }
    }
  }
 	return null
}

相交链表 (opens new window)

编写一个程序，找到两个单链表相交的起始节点。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let h1 = headA
  let h2 = headB
  
  while(h1 !== h2) {
    h1 = h1 ? h1.next : headB
    h2 = h2 ? h2.next : headA
  }
  return h1
}