链表2 - 写链表代码的技巧

0x00 前言

专栏这一讲主要讲解写链表代码的一些技巧，就我的经验来说，链表代码写起来很麻烦，主要是链表的指针指来指去就会变得很混乱，还有就是边界问题的处理，使得链表的处理很麻烦。事实上任何问题的边界问题值得注意。

0x01 技巧

1、理解指针或引用的含义

java中并没有指针，可以理解为引用，常见的有两种

p = q.next
p.next = q

第一句是给p赋值，将p指向q的下一结点
第二句是p下一结点设置为q

2、利用哨兵简化实现难度

在处理边界问题的时候，往往需要针对null进行判断，为了避免每次在循环中判断一次，我们可以在边界就设置好满足的条件，例如：在数组中查找元素key

find(int[] a,int n,int key){
int i = 0
    while (i<n){
        if (a[i] == key){
            return i
        }
        ++i
    }
}
return -1

以上每一次循环都要判断i<n，我们可以在数组末尾处设置哨兵，这样保证数组一定不会越界，然后判断一下就行了

if(a[n-1]==key){
    return n-1
}
tmp = a[n-1]
a[n-1]=key
while (a[i]!=key){
    ++i
}
if (i==n-1){
    return -1
}else {
    reutrn i
}

以上代码在数组末尾设置了一个哨兵，这样相比第一份代码每次循环少判断一次i<n，对于大数据量的情况下，这个累积的效率就很明显了

在链表中的哨兵，经常是设置一个头哨兵，不存储数据，指向链表，可以避免null的检测

3、边界条件处理

常见的边界问题，需要注意一下几种情形

• 如果链表为空，代码能都正常工作
• 如果链表只包含一个结点时
• 如果链表只包含两个结点时
• 代码逻辑在处理头结点和尾结点时

0xff 总结

除了上述几种技巧外，还有画图辅助等方法帮助思考，并且以上几种技巧不仅仅适用于链表，其他数据结构算法的题也都适用，重要的时多些多练，对于链表，有一下几种常见操作需要掌握

• 单链表反转

def reverse(node: Option[Node]): Option[Node] = {
    if (node.isEmpty){
      return node
    }
    var pre:Option[Node] = None
    var current:Option[Node] = node
    while (current.get.next.nonEmpty){
      var tmp:Option[Node] = current.get.next
      current.get.next = pre
      pre = current
      current = tmp
    }
    current.get.next = pre
    current
}

• 链表中环的检测

环的检测使用两个快慢指针完成

image

如图，每次慢指针走一步，快指针走两步，如果有环，那么快慢指针一定会相遇
假设：

起点距离环入口距离为m
环的入口点距离相遇点为k
环长度为n
相遇时，慢指针绕环a圈，快指针绕环b圈
所以，当相遇时，慢指针走了 m+an+k，快指针走了 m+bn+k
根据两个指针的速度，得到 2(m+an+k) = m+bn+k => m+k = (b-2a)n
随便找一组数据都能满足上述等式

def ifCycle(node:Option[Node]):Boolean={
    var slow,fast = node
    while (fast.isDefined && fast.get.next.isDefined){
      slow = slow.get.next
      fast = fast.get.next.get.next
      if (slow==fast){
        return true
      }
    }
    false
 }

我们还可以求环的入口点，当相遇完成后，将慢指针移动到起点，快指针在相遇点，然后快指针和慢指针每次都运动一步，下一次相遇点一定是环的入口点
证明：

当慢指针运动到入口点时，快指针也运动了m步，因为m+k是n的整数倍，所以此时快指针一定距离启动也是a的距离，即入口点

// 不能返回循环的链表，会报StackOverflowError，这里返回入口链表的值，假设链表中的数据都不一样，而且都不是0
def findEntrance(node:Option[Node]): Int ={
    var slow,fast = node
    // cycle记录是否有环 flag记录是否停止循环
    var cycle,flag = false
    while (!flag){
      if (fast.isDefined && fast.get.next.isDefined){
        slow = slow.get.next
        fast = fast.get.next.get.next
        if (slow==fast){
          cycle = true
          flag = true
        }
      }else{
        flag = true
      }
    }
    if (cycle){
      slow = node
      while (slow!=fast){
        slow = slow.get.next
        fast = fast.get.next
      }
      slow.get.data
    }else{
      // 没有环返回0
      0
    }
}

参考资料：链表环检测算法

• 两个有序链表合并

def merge(node1: Option[Node],node2:Option[Node]): Option[Node] ={
    if (node1.isEmpty){
      node2
    }
    if (node2.isEmpty){
      node1
    }
    // small永远指向small和big之间较小的，然后循环比较small的下一个结点和big结点
    var big = node1
    var small = node2
    if (big.get.data < small.get.data){
      small = node1
      big = node2
    }
    // 记录较小的头结点，返回结果
    val head = small
    // 只要small的下一个结点和big不为空，就可以比较
    while (small.get.next.isDefined && big.isDefined){
      if (small.get.next.get.data < big.get.data){
        small = small.get.next
      }else{
        var smallNext = small.get.next
        var bigNext = big.get.next
        small.get.next = big
        big.get.next = smallNext
        // 调整之后 big、smallNext、bigNext中big最小，bigNext最大
        small = big
        big = bigNext
      }
    }
    // 跳出循环有两种情况，1种是small指向了最后一个结点，此时把big接到small的后面就行了
    // 还有一种是big指向null了，此时不用变化，head直接返回就行了
    if (big.isDefined){
      small.get.next = big
    }
    head
  }

• 删除链表倒数第n个结点

// 快慢指针，快指针先走n步，然后快慢指针同时走直到快指针到头
def deleteNode2(node:Option[Node],n:Int): Option[Node] = {
    require(n>0,"n必须大于0")
    var slow,fast = node
    var index = 0
    while (fast.isDefined && index<n){
      index += 1
      fast = fast.get.next
    }
    require(index==n,"至少包含n个结点")
    // 删除头结点
    if (fast.isEmpty){
      return node.get.next
    }
    while (fast.isDefined && fast.get.next.isDefined){
      slow = slow.get.next
      fast = fast.get.next
    }
    slow.get.next = slow.get.next.get.next
    node
 }
// 先反转链表在删除第k个结点，然后在反转链表
def deleteNode(node:Option[Node],n:Int): Option[Node] ={
    var head = ReverseLinked.reverse(node)
    var cur = head
    // 删除头结点
    if (n==1){
      head = head.get.next
      cur.get.next = None
      return ReverseLinked.reverse(head)
    }
    // cur指向删除结点的上一个结点
    for (i <- 1 until n-1){
      cur = cur.get.next
    }
    val tmp = cur.get.next
    cur.get.next = tmp.get.next
    tmp.get.next = None

    ReverseLinked.reverse(head)
 }

• 求链表的中间结点

// 返回中间结点，如果是偶数个结点，返回中间靠右的结点
def findMidNode(node:Option[Node]): Option[Node] ={
    var slow,fast = node
    while (fast.isDefined && fast.get.next.isDefined){
      slow = slow.get.next
      fast = fast.get.next.get.next
    }
    slow
}