数据结构与算法之美四之链表常见操作_c语言 1、单链表反转 2、链表中环的检测 3、两个有序链表的合并 4、删除倒数第k个

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

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

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

思维导图

单链表 Scala 实现

class ListNode(_v: Int) {
  var v: Int = _v
  var next: ListNode = _
}
1
2
3
4

单链表反转

递归

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
  }
}
1
2
3
4
5
6
7
8
9
10

关键

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

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

非递归

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
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

关键

• 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
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

关键

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

环入口

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

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
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

关键

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

• 快指针判空

两个有序的链表合并

递归

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
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关键

• 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
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

关键

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

删除链表倒数第 n 个结点

object Solution {
  def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
    val sentry: ListNode = new ListNode(0)
    sentry.next = head
    var first: ListNode = sentry
    var second: ListNode = sentry
    for (_ <- 1 to n + 1) {
      first = first.next
    }
    while (first != null) {
      first = first.next
      second = second.next
    }
    second.next = second.next.next
    sentry.next
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

关键

• 双指针

求链表的中间结点

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
  }
}
1
2
3
4
5
6
7
8
9
10
11

关键

• 双指针

参考：

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

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

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

个人网站：

https://www.shockang.com