链表问题补充

2018-07-09 本文已影响24人 289346a467da

本篇文章是上篇文章的一个补充数据结构之表的总结

合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序。

链表1: 1 --> 3 --> 5 --> 7

链表2: 2 --> 4 --> 6 --> 8

合并之后的链表： 1-->2-->3-->4-->5-->6-->7-->8

如上所示，首先我们需要分析链表合并的过程：

首先我们从两个链表的头节点开始分析，链表1的头节点小于链表2的头节点，那么链表1的头节点就是合并链表的头节点。然后再用链表1头节点的下一个节点N和链表2的头节点对比，如果链表1的N节点还是小于链表2的头节点，那么，N节点就作为合并链表的下一个节点，然后N节点的下一个节点继续和链表2的头节点对比。如果链表1N节点大于链表2的头节点，那么链表2的头节点作为合并链表的下一个节点，然后链表2的头节点的下一个节点M 和链表1的N节点继续对比，如此得到一个递增排序的新的链表，很明显这是一个典型的递归的过程。

如果你还感觉有点懵懵的，我用下面来这样表示就清楚了。

P1(表示第一个链表)
1 --> 3 --> 5 --> 7

P2(表示第二个链表)
2 --> 4 --> 6 --> 8

 3    5    7

 2    4    6    8

 3   5   7

1-->2

 4   6   8

5   7

1-->2-->3

4   6   8

......

分析完合并过程后，我们还需要来解决鲁棒性的问题。比如空链表的问题，如果第一个链表是空链表而第二个链表不是空链表，那么合并后的新链表就是第二个链表。反之是第一个链表。如果两个链表都为空那么，合并的链表就是空链表。

ok,想清楚合并链表的分析过程和代码的鲁棒性，就可以动手写代码了。

public Node mergeInt(Node pHead1, Node pHead2) {
        if (pHead1 == null) {
            return pHead2;
        } else if (pHead2 == null) {
            return pHead1;
        }
        Node mergeHead = null;
        Integer date1 = (Integer) pHead1.date;
        Integer date2 = (Integer) pHead2.date;
        if (date1 < date2) {
            mergeHead = pHead1;
            mergeHead.next = mergeInt(pHead1.next, pHead2);
        } else {
            mergeHead = pHead2;
            mergeHead.next = mergeInt(pHead1, pHead2.next);
        }
        return mergeHead;
    }

这道题考验了分析问题的能力和代码的鲁棒性。

链表中倒数第k个节点

题目：输出链表倒数第K个节点，且只能遍历链表一次。

当我们看到这个题目的时候得到倒数第k个节点，很自然的就会想到先走到链表的尾端，再从尾端回回朔k步，很简单就能得到。可是本题的链表是单链表，而单链表的节点只有从前往后没有从后往前，这种思路也只能pass掉。

既然不能从尾节点开始遍历，那么我们将思路回到头节点上来。假设整个链表有n个节点，那么倒数第k个节点从头开始数就是 n-k+1节点。首先我们要得到链表中节点的个数n,然后从头节点走 n-k+1 个就行了。但是这要我们就需要遍历两次链表，题目要求只能遍历一次链表。

从上面的分析来看，我们的思路是正确的，但是如何实现一次遍历呢？我们可以定义两个指针，第一个指针从头节点开始遍历向前走k-1步，第二个指针保持不动。从第k步开始，第二个指针从头节点开始遍历，两个指针正好相差k-1步，当第一个指针到达尾节点时，第二个指针正好指向倒数第k个节点。

OK，分析了这么多，我们终于找到了解决办法，那么就可以很快写出下面的代码：

 public Node findKthToTail(Node pHead, int k) {
        Node pA = pHead;
        Node pB = null;
        for (int i = 0; i < k - 1; i++) {
            pA = pA.next;
        }
        pB = pHead;
        while (pA.next != null) {
            pA = pA.next;
            pB = pB.next;
        }
        return pB;
    }

如果你真的是上面这样写的，那么你会被直接pass掉。Why？

上面的那段代码，没有考虑到代码的鲁棒性。

什么是鲁棒性呢？

所谓的鲁棒性就是指程序能够判断输入是否呵护规范要求，并对不符合要求的输入予以合理的处理。

有三种办法可以让上述代码崩溃：

pHead = null
链表的总数小于k
k = 0

这样潜在风险的代码，相信如果你是面试官，你也不会录用的。

修改之后的代码：

public Node findKthToReal(Node pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        Node pA = pHead;
        Node pB = null;
        for (int i = 0; i < k - 1; i++) {
            if (pA.next != null) {
                pA = pA.next;
            } else {
                return null;
            }
        }
        pB = pHead;
        while (pA.next != null) {
            pA = pA.next;
            pB = pB.next;
        }
        return pB;
    }

举一反三：

当我们用一个指针遍历链表不能解决问题时，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度更快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

这道题考验了我们解决问题的思路和代码的鲁棒性。

链表的中间节点,且只能遍历链表一次

如果懂了上面一道题，那么这道题也很简单。是上面那道题的扩展题。

分析：当看到一道题目时，不要着急写代码，先要分析以下。如果链表的总数为奇数则返回中间的节点，如果链表的总数为偶数，则返回中间两个节点的任意一个。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步，当走的快的指针走到链表尾部时，走的慢的指针正好走到了中间节点。

鲁棒性：1. 头节点不能为空。2. 走的快的指针不能为空。

我们很快就能写出代码：

 public Node findMid(Node pHead) {
        if (pHead == null) {
            return null;
        }
        Node pA = pHead;
        Node pB = pHead;
        while (pA.next != null) {
            if (pA.next.next != null) {
                pA = pA.next.next;
                pB = pB.next;
            } else {
                pA = pA.next;
                //可以取前一个或者后一个
                pB = pB.next;
            }
        }
        return pB;
    }

链表中环的入口节点

带中环的链表

如上图所示，
要想解决这个问题：

第一步如何确定一个链表中包含环。

这个问题我们依然可以用两个指针来解决问题，两个指针同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走的快的指针追上了走的慢的指针，那么链表就包含环。如果走的快的指针走到链表的末尾(pNode.next == null),那么链表就不包含环，如果你弄懂上述问题，这一步相信你可以很快写出代码。
第二步如何得到环中节点的个数。
从第一步中可以看出，如果两个指针相遇，那么就一定存在环，且两个指针相遇的节点一定在环中，从这个节点出发，一边移动一边计数，再次回到这个节点，就可以得到环中节点个数了。
第三部如何找到环的入口。

image.png
这一步还是用两个指针来解决问题，P1和P2两个指针指向头节点，P1线在链表上向前移动n(n 就是中环节点的个数也就是第二步得到的个数)步，然后两个指针以相同速度向前移动，它们相遇的节点就是中环的入口节点。

具体实现代码如下：

    /**
     * 找到两个指针相遇的节点
     *
     * @param pHead
     * @return
     */
    public Node findMettingNode(Node pHead) {
        if (pHead == null) {
            return null;
        }

        Node pSolw = pHead.next;
        if (pSolw == null) {
            return null;
        }
        Node pFast = pSolw.next;
        if (pFast == null) {
            return null;
        }

        while (pFast != null && pSolw != null) {
            if (pFast == pSolw) {
                return pFast;
            }

            pSolw = pSolw.next;

            pFast = pFast.next;

            if (pFast != null) {
                pFast = pFast.next;
            }
        }

        return null;
    }

    /**
     * 判断是否存在环，然后计算环的节点个数，最后得到环的入口
     *
     * @param pHead
     * @return
     */
    public Node entryNode(Node pHead) {
        Node mettingNode = findMettingNode(pHead);
        if (mettingNode == null) {
            return null;
        }

        //得到中环节点的数目
        int size = 1;
        Node mettingNode1 = mettingNode;

        while (mettingNode1.next != mettingNode) {
            ++size;
            mettingNode1 = mettingNode1.next;
        }

        //先移动中环节点的次数
        mettingNode1 = pHead;
        for (int i = 0; i < size; i++) {
            mettingNode1 = mettingNode1.next;
        }

        //在移动 1 和 2
        Node mettingNode2 = pHead;

        while (mettingNode1 != mettingNode2) {
            mettingNode1 = mettingNode1.next;

            mettingNode2 = mettingNode2.next;
        }

        return mettingNode1;
    }

链表问题补充

合并两个排序的链表

链表中倒数第k个节点

链表的中间节点,且只能遍历链表一次

链表中环的入口节点

猜你喜欢

热点阅读