Java-数据结构-链表-高频面试题(2)

第一题：分隔链表

📚 思路提示：这题看似需要将很多的结点进行移动转换，但其实用不着这么麻烦。该题的要求是"要我们将小于x的结点都放在左边，大于等于x的结点都放在右边"，那么就说明左边是一类，右边是一类，它们都可以通过某种条件筛选出对应的结点。

所以我们就可以新建两个链表，一个用于存储"值小于x的结点"，另一个用于存储"值大于等于x的结点"，最后再将新表尾的next置为null，返回新表头就好了！

⭐ 图解：

📖 代码示例：

class Solution {
    public ListNode partition(ListNode pHead, int x) {
        ListNode left = new ListNode();
        ListNode right = new ListNode();
        ListNode head = left;
        ListNode end = right;
        while(pHead != null){
            if(pHead.val < x){
                left.next = pHead;
                left = left.next;
            }else{
                right.next = pHead;
                right = right.next;
            }
            pHead = pHead.next;
        }
        right.next = null;
        left.next = end.next;
        return head.next;
    }
}

第二题：合并两个有序链表

📚 思路提示：这题还是比较简单的，思路就和上一道题大同小异~

这题与"分隔链表"有一个共同点就是，都可以创建新链表，通过将题中已给的链表进行遍历，然后将符合条件的结点插入新链表，直到将所有结点都插入新链表~就能够得出我们想要的答案了

而这题显而易见，我们只需要在两者都不为空的前提下遍历两个有序链表，对两个结点的val进行比较，将val小的结点插入新链表，然后继续遍历~最后就能得到两者结合的升序链表啦~

⭐ 图解：

📖 代码示例：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode node = new ListNode();
        ListNode list = node;
        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                list.next = list2;
                list2 = list2.next;
            }else if(list1.val <= list2.val){
                list.next = list1;
                list1 = list1.next;
            }
            list = list.next;
        }
        if(list1 == null){
                list.next = list2;
        }if(list2 == null){
                list.next = list1;
        }
        return node.next;
    }
}

第三题：合并 K 个升序链表

📚 思路提示：此题稍微复杂，并且方法繁多，但是我们上道题已经搞清楚了最核心的基础操作：

合并两个升序链表

而随之我们就需要围绕着这八个字开始解题了~其实最简单的暴力解法就非常简单了，就是将这个链表数组全部遍历，依次将第一个链表和第二个链表结合成有序链表传回，再用此链表与第三个链表结合成有序链表传回...以此类推，就能解决该题：

没错，但是太暴力了！！并且如果这么解题，也对不起它困难的难度评级，那么让我们先考虑一下为何它的时间复杂度如此之高：

⭐ 图解(1)：

从大小为3的链表数组或许看不出什么，但是它的时间损耗是"从链表出现"到"链表数组遍历结束"之间重复进行并且一直存在的，而且它遍历数组需要经历n次(链表数组大小)操作，则第一个和第二个链表需要参与排列n次，第三个需要参与n - 1次...所以当链表数组特别大的时候，这个损耗便不能再忽略。于是吸取这个问题的教训，加以思考：

时间复杂度过高的原因是"链表参与的后续运算过多，排列次数多影响该问题"。

排序好的链表参与后续运算我们是无法改变的，我们只能尽量减少这种损耗，那不妨我们从排列次数入手，我们现在的排列效率为一次只排列第一对儿，这样导致我们大多数的数据都卡在第一个列表，并且参与n多次计算。那此时我们可以将链表数组进行一直分组的操作，同时将被分到一组的链表合并，以此递归，这样就解决了排列次数过多和数据参与多余计算过多的问题了：

(采用分治的方法，通过不断递归取 "mid" 的方法，将 k 个链表分为2组、4组、8组...直到分为 k/2 组(每组两个链表)跳出递归，然后开始不断结合链表，将 k 个链表结合为 k/2 个链表，再变成 k/4 、k/8...直到变成一整个链表，返回该链表)

⭐ 图解(2)：

📖 代码示例：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode list = grouping(lists,0,lists.length - 1);
        return list;
    }
    public ListNode grouping(ListNode[] lists,int l,int r){
        if(l == r){
            return lists[l];
        }
        if(l > r){
            return null;
        }
        int mid = (l + r) >> 1;
        return Merge(grouping(lists,l,mid) ,grouping(lists,mid + 1,r));
    }
    public ListNode Merge(ListNode cur1,ListNode cur2){
        if(cur1 == null){
            return cur2;
        }
        if(cur2 == null){
            return cur1;
        }
        ListNode head = new ListNode();
        ListNode cur = head;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                head.next = cur1;
                head = head.next;
                cur1 = cur1.next;
            }else {
                head.next = cur2;
                head = head.next;
                cur2 = cur2.next;
            }
        }
        if(cur1 == null){
            head.next = cur2;
        }else if(cur2 == null){
            head.next = cur1;
        }
        return cur.next;
    }
}

第四题：两数相加

📚 思路提示：该题的核心也是同时遍历两个链表，将对应单位的和对10取余后插入新链表~并且要记得将计算后结果大于等于10的情况，要在下一位进位哦~，还要记得将进位数置0。

也就是说，如果某一时刻，取出的两个数字分别为 a 和 b ，进位值为 num，那么这位的数字就是 (a + b + num) % 10 ，新的进位制为 (a + b + num) / 10。

(注意：每位数字都是按照 逆序 的方式存储的，即 2->4->3 = 342)

📖 代码示例：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode();
        ListNode head = cur;
        //代表进位数
        int num = 0;
        while(l1 != null || l2 != null){
            int x = 0;
            int y = 0;
            if(l1 != null){
                x = l1.val;
            }
            if(l2 != null){
                y = l2.val;
            }
            int sum = x + y + num;
            //进位数重置
            num = 0;
            if(sum < 10){
                cur.next = new ListNode(sum);
            }else {
                cur.next = new ListNode(sum % 10);
                num++;
            }
            cur = cur.next;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        //防止最后进位
        if(num == 1){
            cur.next = new ListNode(num);
        }
        return head.next;
    }
}

第五题：删除链表倒数第 N 个结点

📚 思路提示：想要学会删除链表倒数第N个结点，我们首先得要能够找到链表的倒数第N个结点，以及知道如何删除链表中的一个结点。

找到链表的倒数第N个结点：

这个思路其实并不难，既然已经给定你N了，那么就很好找了。

比如此时我们想找到链表中的倒数第2个结点(N = 2)，那我们先定义两个结点 cur1 = head 和 cur2 = head，然后我们先让 cur1 走 (N - 1)步，也就是1步，然后两结点同时往后走，等到 cur1 走到最后一个结点时，cur2 此时的位置就是倒数第2个结点了~

⭐ 图解(1)：

删除链表中的一个结点：

这点并不难，我们在之前模拟实现单链表的时候就写过类似的函数，直接看图~

⭐ 图解(2)：

那么将这两个小问题结合起来就能够轻松解决这个问题了：

⭐ 图解(3)：

📖 代码示例：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur0 = head;
        ListNode cur1 = head;
        while(n-- > 0){
            cur0 = cur0.next;
            //代表删除第一个数据
            if(cur0 == null){
                return head.next;
            }
        }
        //找到倒数第N个结点的前一个结点
        while(cur0.next != null){
            cur0 = cur0.next;
            cur1 = cur1.next;
        }
        //跳过倒数第N个结点
        cur1.next = cur1.next.next;
        return head;
    }
}

第六题：两两交换链表中的节点

📚 思路提示：题目看似简单，其实还是有些弯绕的。看到这题的时候或许大家想弄两个结点，然后将 cur2.next = cur1，cur1.next = cur3...等等步骤，但实际上，直接通过第一个和第二个结点就开始对整个链表进行操作，会有很多潜在的问题：

📕 交换 cur1，cur2 时，还需要创建cur3，cur4用来帮助cur1，cur2交换以及向后移动，而从第一个和第二个结点开始，就有可能出现形如：1->2->3->4 ==》2->1->4->3 的情况，也就代表我们的第一个结点要指向第四个结点，因此可能越界访问

📕 从 cur1和cur2开始，无法应对链表长度为2的情况，因为只有链表长度 >= 3，才能够进入循环

所以虽然说，我们可以对"访问第四个结点是否越界"使用条件语句解决，也可以单独将"链表长度为2"的情况解决，但却显得太麻烦了~所以我们换一个思路：

以上问题的出现是因为"访问越界"和"进入循环的链表长度 >= 3"，那我们不妨设计一个 cur0 在 cur1 前面，不再使用 cur1 去访问 cur4，而是通过 cur0 先去调换 cur1 和 cur2 的位置，然后进入下次交换时，"1"已经变成了第二个结点，那么此时再用它去与第四个结点相连，便解决了"访问越界"的问题。

而同样的，因为我们将起始点往回退了一步，这样链表长度为2的链表也能够进入我们的循环进行结点交换了~

⭐ 图解：

📖 代码示例：

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode cur0 = new ListNode(0,head);
        ListNode cur1 = head;
        ListNode Head = cur0;
        while(cur1 != null && cur1.next != null){
            ListNode cur2 = cur1.next;
            ListNode cur3 = cur2.next;
            //交换 1 和 2
            cur0.next = cur2;
            cur2.next = cur1;
            cur1.next = cur3;
            //移动 cur0 和 cur1 
            cur0 = cur1;//第0位 移动到 第2位                 
            cur1 = cur3;//第1位 移动到 第3位
        }
        return Head.next;
    }
}

左边是改良过的，右边是之前的，可以看出代码量和整洁程度差的不是一星半点~

第七题：排序链表

📚 思路提示：还记得我们上面做了一道"合并K个升序链表"的题嘛？那个题和这个题还是有些相似之处的，或许说我们可以用近乎一样的思路去解决它~

首先，我们知道，想通过创建新链表，用迭代的方法将两个链表组合成一个新的有序链表，就要求两个链表也必须是有序链表。

再回看我们这道题，看起来杂乱无章，根本不是有序链表。但我们看到的仅仅是"4->2->1->3"不是有序链表，不妨让我们再仔细看看：将"4->2->1->3"分为"4->2"，"1->3"，然后再将"4->2"，"1->3"分为"4"，"2"，"1"，"3"，这回我们再看~每个链表只有一个结点，这样就能称得上是有序了吧~

接着这个思路，我们就要知道如何将链表从中隔断，没错，就是上一篇练习题中所学习过的"快慢指针"方法，我们可以创建一个"从中隔断链表"的函数，然后通过"归并排序"的方法，将其分成一个个结点，最后再通过"合并两个有序链表"的函数得到一个完整的有序链表~

⭐ 图解：

📖 代码示例：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 找到中间节点
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next = null;
        // 递归排序左右子链表
        ListNode left = sortList(head);
        right = sortList(right);
        // 合并两个有序链表
        return merge(left, right);
    }

    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode cur1, ListNode cur2) {
        ListNode Head = new ListNode();
        ListNode pHead = Head;
        while (cur1!= null && cur2!= null) {
            if (cur1.val < cur2.val) {
                Head.next = cur1;
                cur1 = cur1.next;
            } else {
                Head.next = cur2;
                cur2 = cur2.next;
            }
            Head = Head.next;
        }
        if (cur1!= null) {
            Head.next = cur1;
        } else {
            Head.next = cur2;
        }
        return pHead.next;
    }
}

那么这次关于链表的练习题就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦~