MENU

数据结构(三)单链表 - 进阶

August 1, 2018 • Code

前言:在前面的文章 数据结构(二)单链表 - 基础 中实现了单链表的一些基础题。本文作为扩展,增加了单链表中环、相交及复制的题目。

单链表 & 环

判断单链表是否带环

采用快慢指针法判断链表是否带环。

/**
 * 给出链表头指针,如有环返回交点,否则返回 null
 *
 * @param head
 * @return
 */
public static Node isExistsLoop(Node head) {
    if (head == null) return null;
    Node fast, slow;
    fast = slow = head;
    while (fast.next != null && fast.next.next != null) {
        // 同时步进
        fast = fast.next.next;
        slow = slow.next;
        // 存在交点,有环
        if (fast == slow) return slow;
    }
    return null;
}

求带环单链表的环长度

一个指针固定环中某个节点,另一个指针依次步入,当两者相遇时,指针所走步数即为环长度。

public static int loopLen(Node head) {
    if (head == null) return 0;
    Node point = isExistsLoop(head);
    // 不存在环
    if (point == null) return 0;
    // 存在环
    Node cur, walk;
    cur = point;
    walk = point.next;
    int count = 1;
    while (cur != walk) {
        ++count;
        // 同时步进
        walk = walk.next;
    }
    return count;
}

//测试
public static void main(String[] args) {
    Node head = Node.generate(5);
    /**
     *             +-----------------------------+
     *             v                             |
     * +---+     +---+     +---+     +---+     +---+
     * | 0 | --> | 1 | --> | 2 | --> | 3 | --> | 4 |
     * +---+     +---+     +---+     +---+     +---+
     */
    head.next.next.next.next.next = head.next;
    Node existsLoop = isExistsLoop(head);
    Node.printNodeOne(existsLoop);
    System.out.println("Loop length is: " + loopLen(head));
    Node.printNodeOne(getEnterPoint(head));
}

求带环单链表的环入口点

假设 head 到入口点的距离为 x,入口点到快慢指针交点的距离为 y,慢指针到交点所走的距离为 S,易得 \(S = x + y\)。

因为慢指针与快指针相遇时慢指针在环中所行距离没有一圈。

快指针到相交点时所行距离为 2S,设环的长度为 r,此时快指针在环中已走 nr 步,n 为圈数,大于 0。易得 \(2S = x + nr + y\)。

综合上面两式可得 \(x = nr - y\)。

故一指针从头节点出发,一指针从快慢指针交点出发,同时步进 x 步,两指针必定相遇,相遇处即为入口点。

因为环中指针从交点(离入口点 y 步)出发,步进 x 步,相当于 nr - y 步,即循环 n 圈后倒退 y 步,正好到达入口点,与从头节点出发的指针相遇。

public static Node getEnterPoint(Node head) {
    if (head == null) return null;
    Node point = isExistsLoop(head);
    // 不存在环
    if (point == null) return null;
    // 存在环
    Node cur = head;
    while (point != cur) {
        cur = cur.next;
        point = point.next;
    }
    return point;
}

单链表 & 相交

判断两个链表是否相交,若相交,求交点。

主要分为链表不带环链表带环两种情况。

链表不带环

计算两链长度,计算长度差 k,从长链出发步进 k 步,再两链同时步入,相遇交点即为交点,没有交点即不相交。

如果只简单判断是否相交,则比较两链最后结点是否相同即可。

/**
 * 判断两个单链表是否有交点,如果有,返回交点(两个链表没有环)
 *
 * @param h1
 * @param h2
 * @return
 */
public static Node findPointWithoutCycle(Node h1, Node h2) {
    // 某一链为空,必定没有交点
    if (h1 == null || h2 == null) return null;
    int count1 = 1;
    int count2 = 1;
    Node l = h1;
    Node s = h2;
    // 统计两链长度
    while (l.next != null) {
        ++count1;
        l = l.next;
    }
    while (s.next != null) {
        ++count2;
        s = s.next;
    }

    // 确保 l 指向长链
    l = count1 < count2 ? h2 : h1;
    s = count1 < count2 ? h1 : h2;

    // 长链先行
    for (int i = 0; i < Math.abs(count1 - count2); ++i) {
        l = l.next;
    }
    while (l != s && l.next != null && s.next != null) {
        l = l.next;
        s = s.next;
    }
    // 相同即为交点
    if (l == s) return s;
    // 不相交
    return null;
}
    
// 例子
    public static void main(String[] args) {
    /**
     * 例子一:无环
     *
     * +---+     +---+     +---+     +---+     +---+     +---+     +---+
     * | 0 | --> | 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 | --> | 6 |
     * +---+     +---+     +---+     +---+     +---+     +---+     +---+
     *                                                     ^
     *                                                     |
     *                                                     |
     * +---+     +---+                                     |
     * | 7 | --> | 8 | ------------------------------------+
     * +---+     +---+
     */
    Node h1 = Node.generate(7);
    Node<Integer> h2 = new Node<>(7);
    h2.next = new Node<>(8);
    h2.next.next = h1.next.next.next.next.next;
    Node pointWithoutCycle = findPointWithoutCycle(h1, h2);
    Node.printNodeOne(pointWithoutCycle);
}

链表可能带环

所有可能的情况如下:

如果单链表相交并且带环,则环一定处于相交部分中。

步骤:

  • 判断两链是否有环,如果都无环或一链有环一链无环则必定无交点。
  • 若两链都有环,判断是否为同一环。不为同一环则无交点。
  • 如果为同一环则判断环入口点是否相同,相同则交点位于环入口点处或环外,直接去掉环,再进行上面无环链表求交点的操作;如果入口点不同,则两个入口点即为交点

代码如下:

/**
 * 判断两个单链表是否有交点,如果有,返回交点(两个链表有环)
 *
 * @param h1
 * @param h2
 * @return
 */
public static List<Node> findPointWithCycle(Node h1, Node h2) {
    // 某一链为空,必定没有交点
    if (h1 == null || h2 == null) return null;
    Node e1 = ChainLoop.isExistsLoop(h1);
    Node e2 = ChainLoop.isExistsLoop(h2);
    List<Node> list = new ArrayList<>();
    // 两链无环,调用上面的方法即可
    if (e1 == null && e2 == null) {
        list.add(findPointWithoutCycle(h1, h2));
        return list;
    }
    // 两链中一条有环,一条无环,则一定没有交点,因为如果存在环并且有交点,则一定为共享环
    if (e1 == null || e2 == null) return list;
    // 两链都有环,判断是否是同一个环
    Node cur = e1;
    while (cur.next != null) {
        if (cur == e2) break;
        cur = cur.next;
        if (cur == e1) return list;
    }
    // 同环判断环入口点位置是否相同,以此判断两链相交情况
    Node p1 = ChainLoop.getEnterPoint(h1);
    Node p2 = ChainLoop.getEnterPoint(h2);
    if (p1 == p2) {
        // 环入口点相同,说时此时两链交点在环外或环入口点上,去掉环部分,求无环的两链交点即可
        p1.next = null;
        list.add(findPointWithoutCycle(h1, h2));
        return list;
    }
    // 环入口点不同,则两个入口点都是交点,
    list.add(p1);
    list.add(p2);
    return list;
}
    
// 例子
public static void main(String[] args) {
    /**
     * 例子二
     *                       +-----------------------------+
     *                       v                             |
     * +---+     +---+     +---+     +---+     +---+     +---+
     * | 0 | --> | 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 |
     * +---+     +---+     +---+     +---+     +---+     +---+
     *             ^
     *             |
     *             |
     *           +---+
     *           | 6 |
     *           +---+
     */
    Node h3 = Node.generate(6);
    h3.next.next.next.next.next.next = h3.next.next;
    Node<Integer> h4 = new Node<>(6);
    h4.next = h3.next;
    List<Node> pointWithCycle = findPointWithCycle(h3, h4);
    for (Node node : pointWithCycle) {
        Node.printNodeOne(node);
    }
}

复杂链表的复制

一个链表的每个节点,有一个指向 next 指针指向下一个节点,还有一个 random 指针指向这个链表中的一个随机节点或者 NULL,现在要求实现复制这个链表,返回复制后的新链表。

最简单的做法是将 next 与 random 分两组复制:

  • next 指针的复制直接操作即可,时间复杂度为 \(O(n)\) 。
  • random 指针每次复制都需要遍历整个链表,以确定指向的节点在链表中的位置,所以复制 n 个节点所需时间复杂度为 \(O(n^{2})\)。
  • 总的时间复杂度为 \(O(n^{2})\)。

下面采用一种时间复杂度为 \(O(n)\)、空间复杂度为 \(O(1)\) 的方法:

  • 在每个链表节点后面插入克隆节点。
  • 将链表节点中 random 指针的对应关系复制到克隆节点上。
  • 将链表拆分成原来链表和克隆链表。

主要过程

复杂实现 - CNode

相对于 Node 类,CNode 增加了 random 指针。

/**
 * @author kbrx93
 */
public class CNode<T> {

    /**
     * 存储的数据
     */
    public T data;

    /**
     * 下一节点指针
     */
    public CNode next;

    /**
     * 随机指针
     */
    public CNode random;

    public CNode(T data, CNode next, CNode random) {
        this.data = data;
        this.next = next;
        this.random = random;
    }

    public CNode(T data) {
        this(data, null, null);
    }

    public CNode(T data, CNode next) {
        this(data, next, null);
    }

    @Override
    public String toString() {
        return "CNode{" +
                "data=" + data +
                ", next=" + next +
                ", random=" + random +
                '}';
    }
}

代码实现

public class CopyComplexChain {

    /**
     * 返回复杂链表的副本头结点
     */
    public static CNode execute(CNode h) {
        if (h == null) return null;
        // 1. 在复制每个节点并插在对应节点之后
        CNode cur = h;
        do {
            CNode<Object> cloneNode = new CNode<>(cur.data, cur.next);
            cur.next = cloneNode;
            cur = cloneNode.next;
        } while (cur != null);

        // 2. 复制随机指针到对应 clone 节点上
        CNode cloneCur = h.next;
        cur = h;
        while (true) {
            if (cur.random != null) cloneCur.random = cur.random.next;
            cur = cloneCur.next;
            if (cur != null) cloneCur = cur.next;
            else break;
        }

        // 3. 拆分
        cur = h;
        CNode cloneHead = cloneCur = h.next;
        while (true) {
            cur.next = cloneCur.next;
            cur = cur.next;
            if (cur != null) {
                cloneCur.next = cur.next;
                cloneCur = cloneCur.next;
            } else {
                break;
            }

        }
        return cloneHead;
    }

    public static void main(String[] args) {
        /**
         *
         *             +-------------------+
         *             |                   v
         * +---+     +---+     +---+     +---+     +---+
         * | 0 | --> | 1 | --> | 2 | --> | 3 | --> | 4 |
         * +---+     +---+     +---+     +---+     +---+
         *                       |                   ^
         *                       +-------------------+
         *
         */
        CNode<Integer> h = new CNode<>(0);
        CNode cur = h;
        for (int i = 1; i < 5; ++i) {
            cur.next = new CNode<>(i);
            cur = cur.next;
        }
        h.next.random = h.next.next.next;
        h.next.next.random = h.next.next.next.next;

        CNode execute = execute(h);
        System.out.println(execute);
    }
}
  • 结果
CNode
{data=0, next=CNode
    {data=1, next=CNode
        {data=2, next=CNode
            {data=3, next=CNode
                {data=4, next=null, random=null},
            random=null
            },
        random=CNode{data=4, next=null, random=null}
        }, 
    random=CNode{data=3, next=CNode{data=4, next=null, random=null}, random=null}
    },
random=null
}
Archives QR Code
QR Code for this page
Tipping QR Code