链表设计及其相关算法问题

文章目录

1. 链表的分类
2. 链表的操作
1. 2.1. 链表基础元素的定义
3. 一些链表操作的技巧
4. 关于单元测试案例

一说到Linked List你会想到什么？
ArrayList? 看来你是个Java粉。
其实Linked List 并非完全是Java集合包下的LinkedList类，而是一种很基础的数据结构，很多数据结构和算法都由它演化而来，在很多地方我们称它为链表。

链表的分类

按照节点的指针方向这个维度我们将链表划分为：

单向列表
双向列表

由单向列表作简单的改进我们就得到了树这个数据结构，当然作更多改进和约束我们就得到各种性质的树，如果这样的“树”还有回环（当然如果有回环那就不是树的定义了）那就构成了有向图。
由双向列表可以构建目前很受热捧的skiplist(译作：跳表) 数据结构，这种数据结构有很大的希望会取代Red-Black tree（译作：红黑树）成为新的Hashmap的内部实现，它具有Red-Black tree 的各种操作的效率的同时还在rebalance的操作效率上要高于 Red-Black tree。

链表的操作

相信看过我文章的同学就会知道这时候是祭出代码的时候了。
其实在动手写代码前做好一些准备工作是更为重要的，因为这个数据结构是一个比较通用的框架类，关于这个类的分析和设计其实已经比较成熟，所以这里就偷懒直接使用现成结论就好。
由于篇幅的原因下文仅以单向列表为例程作解说，双向列表的实现会在github工程中公布。

链表基础元素的定义

节点：

public class SingleLinkedNode {
    private int value;
    private SingleLinkedNode next;

    public SingleLinkedNode() {}

    public SingleLinkedNode(int value, SingleLinkedNode next) {
        super();
        this.value = value;
        this.next = next;
    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public SingleLinkedNode getNext() {
        return next;
    }

    public void setNext(SingleLinkedNode next) {
        this.next = next;
    }
}

链表类定义：

public class SingleLinkedList {

  private  SingleLinkedNode mHeadNode;
  private  int    mSize;

  public SingleLinkedList(){
      super();
  }

  public SingleLinkedNode getHeadNode() {
      return mHeadNode;
  }

  public int getSize() {
      return mSize;
  }

  public void clearList() {
      this.mHeadNode = null;
  }
}

这个头节点(headNode)是链表访问的入口，也是链表的一个重要属性。
下面就需要考虑链表的一些通用操作了，首先想到的就是增查删
好我们分别来实现它们：
添加:

/**
 *  Append the node to the tail of the link
 *
 * @param value
 */
public void appendNodeToTail(int value){
    if (this.mHeadNode == null) {
        this.mHeadNode = new SingleLinkedNode();
    }

    SingleLinkedNode n = this.mHeadNode;
    SingleLinkedNode node = new SingleLinkedNode();
    node.setValue(value);
    while (n.getNext() != null) {
        n = n.getNext();
    }

    n.setNext(node);
    mSize ++;
}

查找：

/**
 *  Search for the node with the specific value
 *
 * @param value
 * @return
 */
public SingleLinkedNode searchNode(int value) {
    if (this.mHeadNode == null) return null;

    SingleLinkedNode n = this.mHeadNode;

    while (n.getNext() != null && n.getNext().getValue() != value) {
        n = n.getNext();
    }

    return  n.getNext();
}

删除：

/**
 *  Delete the node from the list
 *
 * @param value
 */
public void deleteNode(int value) {
    if (this.mHeadNode == null) return;

    SingleLinkedNode n = this.mHeadNode;

    while (n.getNext() != null && n.getNext().getValue() != value) {
        n = n.getNext();
    }

    if (n.getNext() != null && n.getNext().getValue() == value){
        mSize --;
    }

    n.setNext(n.getNext() != null ? n.getNext().getNext() : null);

}

当然还有必不可少的部分就是测试工程部分：github测试工程链接

如果你认为链表操作就这么简单，那就差的太远了，以上的这些操作应当都是需要很快写出，并且bug-free的，对，bug-free，就是一气呵成，没有bug的意思。
下面说几个跟链表相关，需要些技巧才能搞定的题目。

一些链表操作的技巧

判断链表是否有环

原题传送门

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

好，拿到题目首先要做什么？
审题
有人会说，就这一句话的题目会有什么可以审的？恰恰是因为就一句话才会有大坑。
首先只是说给到一个Linked list，这时候你的本能反应应当是：是单向的还是双向的？对于这道题来说隐喻是单向的。

题目审完了，我们下一步该做什么？
列出可能的所有解决方案
在不考虑不使用辅助空间的限制的情况下，

首先想到的是判断重复的问题应当使用判断重复的数据结构来解决问题，
其次就是需要使用到一个小技巧来判断
相信使用判断重复的数据结构的方法大家都已经想到该怎么做了，所以这部分我们直接贴代码；
下面来讲解下小技巧解决问题的思路：
是否有环会影响到什么？如果是有环的，那么遍历一圈后还是会回到之前遍历过的节点，而如果列表没有环，那么永远都不会出现相遇的情况。
想一想这种特点在我们日常生活的什么东西很像？
钟表的分针，秒针的转动，因为时针、秒针的角速度不同所以在围绕一个圆圈转动的时候就一定会相遇，所以受到这个启发就会有下面这种解法：

/**
 * Judge the LinkedList has cycle (no auxiliary space version)
 *
 * @return
 */
public boolean hasCycle() {
    if (mHeadNode == null) return false;
    SingleLinkedNode normal = mHeadNode;
    SingleLinkedNode fast = mHeadNode;
    while(normal.getNext() != null && fast.getNext() != null && fast.getNext().getNext() != null) {
        normal = normal.getNext();
        fast = fast.getNext().getNext();
        if (normal == fast) return true;
    }

    return false;
}

上面是不需要额外存储空间的解决方案，下面我们看看使用额外空间的解法是怎样的？

/**
 * Judge the LinkedList has cycle (auxiliary space version)
 *
 * @return
 */
public boolean hasCycle2() {
    if (mHeadNode == null) return false;
    HashMap<SingleLinkedNode, SingleLinkedNode> tempMap = new HashMap();
    SingleLinkedNode p = mHeadNode;

    while (p.getNext() != null) {
        if (tempMap.get(p) == null) {
            tempMap.put(p,p);
        } else {
            tempMap.remove(p);
        }
//            Actually this code have the same effect with above 5 lines code.
//            SingleLinkedNode value = tempMap.get(p) == null ? tempMap.put(p,p) : tempMap.remove(p);

        if (tempMap.size() == 0) return true;

        p = p.getNext();
    }

    return false;
}

两种方案都已经写出来了，下面要做什么？
复杂度分析
对于未使用额外辅助方案的算法，实际上是使用了两个速率不同的指针来做的遍历访问，所以时间复杂度为$O(n)$, 空间复杂度上没有使用额外的空间。
对于使用 HashMap 作为辅助空间的算法，由于HashMap的 get() put() remove() size() 函数的时间复杂度都是常数级的，所以这段算法的时间复杂度为$O(n)$, 空间复杂度上使用了长度为n的额外空间所以为$O(n)$
根据以上的分析我们不难选择未使用额外存储的快慢指针方法更优。

复杂度分析过后我们需要作的就是
测试
这里的case也没有太多要说明的， happy case, other case 具体的case参照测试工程github测试工程

反转Linkedlist

原题传送门

Reverse a singly linked list

审题，这里需要注意下为空的情况。
可能的解法会有哪些？
这道题其实会有两种直觉算法：

递归
复杂度分析：
时间复杂度：由于需要遍历所有节点，所以为$O(n)$
空间复杂度：没有使用额外空间
循环
复杂度分析：
时间复杂度：同递归实现相同 $O(n)$
空间复杂度：没有使用额外空间

那么我们来分别实现这两个版本：
递归版本：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode next = head.next;
    ListNode newHeadNode = reverseList(next);
    next.next = head;
    head.next = null;
    return newHeadNode;
}

循环版本：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode pivot = head;
        ListNode frontier = null;
        while (pivot != null && pivot.next != null)
        {
            frontier = pivot.next;
            pivot.next = pivot.next.next;
            frontier.next = head;
            head = frontier;
        }
        return head;
    }

合并两个已排好序的列表

原题传送门

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

首先审题，这道题陷阱应该不多，比如考虑这两个list为空的情况应该怎样处理，都为空，其中一个为空？

可能的解法会有那些？
直接想到的会有两个

直觉算法，创建一个新的列表，然后不断从两个列表内找出最小值，然后顺序加入新列表。

复杂度分析：
时间复杂度：需要遍历两个列表的所有元素，有且仅有一次，因此为$O(n)$
空间复杂度：需要额外的空间存储新的列表，因此为$O(n)$
递归算法，我们来分析下上面算法的过程会发现，其实存在递归的特性，只需要找出列表的头节点最小节点，然后将最小节点的next指向下一层的两个列表就可以。

复杂度分析：
时间复杂度：和上面的算法一样，同样需要遍历所有元素，所以时间复杂度为$O(n)$
空间复杂度：不需要额外的空间存储

显然后面的递归算法更优，那么就按照上面的分析实现：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode resultNode = null;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            resultNode = l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            resultNode = l2;
        }

        return resultNode;
    }
}

由于这个问题相对简单些，所以一气呵成。
bug free，代码优化空间有倒是有，但是会影响可读性，所以暂且认为这就是最后的答案吧。
写完以后想想似乎这个问题还有一个解答，因为一般来说，有了递归的版本就会有个对应的循环的版本，那么好，我们来实现这个循环版本。

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = new ListNode(0);
        ListNode node = head;

        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }

        node.next = l1 != null ? l1 : l2;
        return head.next;
    }
}

因为上面的这种非递归的实现方式相比于递归的方式会少占用栈空间，所以从效率的角度来看是最优的，但是与递归的实现相比，递归的代码可读性更好，所以在效率要求并不高的场景下我更推荐使用递归的实现，如果对栈空间有资源限制那就使用非递归的版本。
之所以拿这个问题出来的原因是，这个问题有很多使用场景，以及它的变形形式的问题有很大的应用空间。
合并两个排序列表的直接使用场景是什么？对！归并排序，在对两个子序列排序后就可以用到这个。
稍微变形下就可以引出下一个更具有通用意义的问题：

合并k个已排序的列表

原题传送门

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

和合并两个排序列表的问题相似，我们还是要审题，然而这个问题的坑并不是那么多，这个环节就暂且略过。
好，我们来看会有那些可能的算法。
首先，直觉算法就是：开辟一个新的空间用来存储合并后的列表，然后递归的去寻找这k个列表的最小的值然后将对应的节点添加到新的列表里。

复杂度分析：
时间复杂度：就如merge两个列表的问题一样，算法需要遍历所有列表元素，所以复杂度为$O(n)$
空间复杂度：使用到了额外的空间，复杂度为$O(n)$

其次，考虑到k个的问题一般都会有递归的算法，仔细分析后我们惊喜地发现的确可以这样来做，思路就是将数组一分为二，然后对这两个子数组分别进行merge，最后得到两个merge过的数组，然后将这两个merge就可以。

复杂度分析：
时间复杂度：该算法将问题划分为两个子问题，然后再加上一个$O(n)$复杂度的子问题，使用master theorem 我们知道这个问题的时间复杂度是$O(nlogn)$
空间复杂度：未使用额外空间
分析过后，后一种的方案目前最优，所以我们来实现这个算法。

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        int len = lists.length;
        int mid = len / 2;

        ListNode leftNode = mergeKLists(Arrays.copyOfRange(lists, 0, mid));
        ListNode rightNode = mergeKLists(Arrays.copyOfRange(lists, mid, len));
        return _merge2List(leftNode, rightNode);
    }

    private ListNode _merge2List(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode result = null;
        if (l1.val < l2.val) {
            l1.next = _merge2List(l1.next, l2);
            result = l1;
        } else {
            l2.next = _merge2List(l1, l2.next);
            result = l2;
        }

        return result;
    }
}

上面的merge2list实现是递归的实现，如果碰到栈溢出问题的话可以使用循环的实现，如下所示：

private ListNode _merge2List(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode head = new ListNode(0);
    ListNode node = head;

    while(l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            node.next = l1;
            l1 = l1.next;
        } else {
            node.next = l2;
            l2 = l2.next;
        }

        node = node.next;
    }

    node.next = l1 != null ? l1 : l2;

    return head.next;
}

上面的代码是否还有优化的空间呢？在我看来已经可以了，再优化可能会影响可读性，因此到这个阶段就可以了。

关于单元测试案例

对于链表的测试其实根据具体情况的不同边界条件和对应业务测试会有所不同，总的来说对于链表的测试我会从以下这几个用例考虑：

链表是空节点 SingleLinkedListNoNodeTest github link
链表含有一个节点 SingleLinkedListOneNodeTest github link
链表含有两个及以上节点 SingleLinkedListTest github link

特别的对于合并链表的问题会有特别的测试用例SingleLinkedListTwoListTes github link

EOF