数据结构与算法之美四之链表常见操作

数据结构与算法之美四之链表常见操作

Scroll Down

​ 在学习极客时间的《数据结构与算法之美》专栏时,王争老师提到只要掌握5 个常见的链表操作,就再也不会害怕写链表代码。

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点

说实话,当时听到这里,我立马就激动了,开干!

思维导图

在这里插入图片描述

单链表 Scala 实现

class ListNode(_v: Int) {
  var v: Int = _v
  var next: ListNode = _
}

单链表反转

递归

object ReverseList {
  def reverse(head: ListNode): ListNode = {
    if (head == null || head.next == null) return head
    val temp: ListNode = head.next
    val newHead: ListNode = reverse(head.next)
    temp.next = head
    head.next = null
    newHead
  }
}

关键

  • 先递归再运算的典型——反转链表

  • 不要大脑模拟每一步,只考虑每次递归

非递归

object ReverseList {
  def reverse(head: ListNode): ListNode = {
    var pre: ListNode = null
    var next: ListNode = null
    var node: ListNode = head
    while (node != null) {
      next = node.next
      node.next = pre
      pre = node
      node = next
    }
    pre
  }
}

关键

  • pre,node,next

  • next 只是存储引用

  • node.next = pre

链表中环的检测

object Circular {
  def isCircular(head: ListNode): Boolean = {
    if (head == null || head.next == null) return false
    var slow: ListNode = head
    var fast: ListNode = head
    while (fast != null && fast.next != null) {
      slow = slow.next
      fast = fast.next.next
      if (slow == fast) return true
    }
    false
  }
}

关键

  • 快慢指针
  • 边界条件:只考虑快指针

环入口

环入口问题虽然老师没有提到,但是我感觉和上面的链表中环的检测是息息相关的

def getCircularEntry(head: ListNode): ListNode = {
    if (head == null || head.next == null) return null
    var slow: ListNode = head
    var fast: ListNode = head
    breakable(
      while (fast != null && fast.next != null) {
        slow = slow.next
        fast = fast.next.next
        if (slow == fast) break
      }
    )
    if (fast == null || fast.next == null) return null
    while (slow != fast) {
      slow = slow.next
      fast = fast.next
    }
    slow
  }

关键

  • 相遇点 到 环入口 的距离 == 链表起点 到 环入口 的距离

  • 快指针判空

两个有序的链表合并

递归

object MergeList {
  def merge(node1: ListNode, node2: ListNode): ListNode = {
    if (node1 == null && node2 == null) return null
    if (node1 == null) return node2
    if (node2 == null) return node1
    var head: ListNode = null
    if (node1.v > node2.v) {
      head = node2
      head.next = merge(node1, node2.next)
    } else {
      head = node1
      head.next = merge(node1.next, node2)
    }
    head
  }
}

关键

  • head 存储一个栈帧里面的较小值引用

  • 临界判空

非递归

object MergeList {
  def merge(node1: ListNode, node2: ListNode): ListNode = {
    if (node1 == null && node2 == null) return null
    if (node1 == null) return node2
    if (node2 == null) return node1
    val flag: Boolean = node1.v < node2.v
    val head: ListNode = if (flag) node1 else node2
    var cur1: ListNode = if (flag) node1 else node2
    var cur2: ListNode = if (flag) node2 else node1
    var pre: ListNode = null
    var next: ListNode = null
    while (cur1 != null && cur2 != null) {
      if (cur1.v < cur2.v) {
        pre = cur1
        cur1 = cur1.next
      } else {
        next = cur2.next
        pre.next = cur2
        cur2.next = cur1
        pre = cur2
        cur2 = next
      }
    }
    pre.next = if (cur1 == null) cur2 else cur1
    head
  }
}

关键

  • cur1 表示两个链表中头结点较小者
  • pre表示cur1 链表的前一个元素
  • next 表示 cur2 链表的后一个元素
  • 临界处理:pre.next = if (cur1 == null) cur2 else cur1

删除链表倒数第 n 个结点

object Solution {
  def removeNDesc(head: ListNode, n: Int): ListNode = {
    val H: ListNode = head
    var first: ListNode = head
    var second: ListNode = head
    for (_ <- 0 to n) {
      first = first.next
    }
    while (first != null) {
      first = first.next
      second = second.next
    }
    second.next = second.next.next
    H
  }
}

关键

  • 双指针

求链表的中间结点

object Solution {
  def midOfListNode(head: ListNode): ListNode = {
    var slow:ListNode = head
    var fast:ListNode = head
    while(fast != null && fast.next != null){
      slow = slow.next
      fast = fast.next.next
    }
    slow
  }
}

关键

  • 双指针

参考:

理解单链表的反转(java实现)

java实现两个有序单链表合并

判断单链表是否有环并找到环的入口等问题

个人博客:

CSDN