【数据结构】单链表面试题讲解-＞贰

àì夳堔傛蜴生んèń 2024-04-17 10:43 65阅读 0赞

#### 文章目录 ####

*  ?引言
 *  ?\[合并两个有序链表\](https://leetcode.cn/problems/merge-two-sorted-lists/description/)
 *   *  ?题目描述
     *  ?示例：
     *  ?解法思路
     *   *  ?建立虚拟节点
         *  ?tmp的建立
         *  ?进行合并
         *  ?链表为空
     *  ?完整代码实现
 *  ?\[链表分割\](https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking)
 *   *  ?题目描述
     *  ?示例：
     *  ?思路解析：
     *   *  ?链表拆分
         *  ?链表a的建立
         *  ?链表b的建立
         *  ?链表的合并
     *  ?完整代码实现
 *  ⭕总结

## ?引言 ##

单链表的操作算法是笔试面试中较为常见的题目。  
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 \_?  
![在这里插入图片描述][94b094fa0d0f42bcac0a437a41e1eff4.png]

## ?[合并两个有序链表][Link 1] ##

### ?题目描述 ###

将两个升序链表合并为一个新的 升序 链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。

### ?示例： ###

![在这里插入图片描述][17b9a8823c0243f284ca8a1e18b8d35a.png]

### ?解法思路 ###

#### ?建立虚拟节点 ####

建立一个虚拟节点为newList；

建立虚拟节点的目的：

*  既然需要合并那么肯定是需要一个头节点
 *  由于两个链表的头节点谁大谁小不知道，所以建立虚拟节点
 *  小的就与虚拟节点相连
 *  ![在这里插入图片描述][49f28bff580543b285c166870f26fbca.png]
 *  最后返回newList.next；

#### ?tmp的建立 ####

虚拟节点不便移动，需要记录当前位置，最后返回newList.next;

那我们就需要一个指针可以向后移动，连接list1与list2比较的较小值

#### ?进行合并 ####

合并思想：

*  对list1与list2里的元素进行比较
 *  谁小就与tmp连接，然后小的list向后走一步成为新的list1，tmp向后走一步成为新的tmp
 *  依次类推进行比较
 *  比如list1的值小，就将list1与tmp相连
 *  然后list1与tmp各自向后走一步
 *  ![在这里插入图片描述][5df5cae331af450391989eb7dea99d6f.png]

结束条件：当list1为null或者list2wei空时

代码实现如下：

while(list1 != null && list2 != null) {
        
                if(list1.val < list2.val) {
        
                    tmp.next = list1;
                    tmp = tmp.next;
                    list1 = list1.next;
                } else {
        
                    tmp.next = list2;
                    tmp = tmp.next;
                    list2 = list2.next;
                }
            }

#### ?链表为空 ####

链表为空分为两种种i情况

一个链表为空

*  只需要将另一个链表连接在tmp后面就好

两个都为空

*  其实上述将另一链表连接在tmp就可以解决
 *  如果连接链表为null，返回的自然也就是null

### ?完整代码实现 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
             ListNode newList = new ListNode();
            ListNode tmp = newList;
            while(list1 != null && list2 != null) {
        
                if(list1.val < list2.val) {
        
                    tmp.next = list1;
                    tmp = tmp.next;
                    list1 = list1.next;
                } else {
        
                    tmp.next = list2;
                    tmp = tmp.next;
                    list2 = list2.next;
                }
            }
            if(list1 == null) {
        
                tmp.next = list2;
            }
            if(list2 == null) {
        
                tmp.next = list1;
            }
            return newList.next;
        }
    }

## ?[链表分割][Link 2] ##

### ?题目描述 ###

现有一链表的头指针 ListNode\* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前

且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

### ?示例： ###

![在这里插入图片描述][848ea39f51544b679d46fc569f1f62a4.png]

### ?思路解析： ###

#### ?链表拆分 ####

将该链表拆分为两个链表；

*  链表a用于存储小于x的数
 *  链表b用于存储大于x的数

最后将链表b拼接在链表a后面，返回a链表的头指针即可

#### ?链表a的建立 ####

创建a1为a链表的头指针，a2为a链表最后一个节点的指针

建立过程：

*  对所需要分割的链表进行遍历
 *  对每一个节点的元素大小进行判断，如果小于x就进入该链表
 *  进入后对我们的a1进行判断，判断a1当前是否为null
 *  如果为null，将当前的pHead赋给a1和a2；
 *  ![在这里插入图片描述][c433663c6a6b46f1ac32c4a6f5a278f6.png]
 *  如果不为null，将当前的pHead赋给a2.next，a2向后走一步
 *  ![在这里插入图片描述][b463b1fa84aa4fbba0246bd8f36ef80c.png]

代码实现如下：

if (a1 == null) {
        
    	a1 = pHead;
    	a2 = pHead;
    } else {
        
    	a2.next = pHead;
    	a2 = a2.next;
    }

#### ?链表b的建立 ####

创建a1为a链表的头指针，a2为a链表最后一个节点的指针

创建过程与链表a同理

代码实现如下：

if (b1 == null) {
        
    	b1 = pHead;
    	b2 = pHead;
    } else {
        
    	b2.next = pHead;
    	b2 = b2.next;
    }

#### ?链表的合并 ####

情况考虑：

*  链表a为null或者两者都为null
 *  这时候只需要返回b1就可以了；
 *  
 *  当a链表不为空时，b链表为空时
 *  将b1赋给a2.next，进行合并
 *  
 *  当a链表不为null时，b链表也不为null
 *  b1赋给a2.next，进行合并
 *  将b2.next置为null，作为尾节点；

代码实现如下：

if (a1 == null) {
        
                return b1;
            }
            a2.next = b1;
            if (b1 != null) {
        
                b2.next = null;
            }
            return a1;

### ?完整代码实现 ###

import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Partition {
        
        public ListNode partition(ListNode pHead, int x) {
        
            // write code here
            ListNode a1 = null;
            ListNode a2 = null;
            ListNode b1 = null;
            ListNode b2 = null;
            while (pHead != null) {
        
                if (pHead.val < x) {
        
                    if (a1 == null) {
        
                        a1 = pHead;
                        a2 = pHead;
                    } else {
        
                        a2.next = pHead;
                        a2 = a2.next;
                    }
                } else {
        
                    if (b1 == null) {
        
                        b1 = pHead;
                        b2 = b1;
                    } else {
        
                        b2.next = pHead;
                        b2 = b2.next;
                    }
                }
                pHead = pHead.next;
            }
            if (a1 == null) {
        
                return b1;
            }
            a2.next = b1;
            if (b1 != null) {
        
                b2.next = null;
            }
            return a1;
        }
    }

## ⭕总结 ##

关于《【数据结构】单链表面试题讲解->贰》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[94b094fa0d0f42bcac0a437a41e1eff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/d0518b107faa4570bf96a0e6745b8ab0.png
[Link 1]: https://leetcode.cn/problems/merge-two-sorted-lists/description/
[17b9a8823c0243f284ca8a1e18b8d35a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/8e0c2ea922344afbb69e9b384ac78434.png
[49f28bff580543b285c166870f26fbca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/8b4e219120de41b193e0b637ab3682cb.png
[5df5cae331af450391989eb7dea99d6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c6b2fc92c68c4a428c2a65ca29669082.png
[Link 2]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[848ea39f51544b679d46fc569f1f62a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/8db8882fc3054d29b37ad6957f8ac93e.png
[c433663c6a6b46f1ac32c4a6f5a278f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/86425e91bf9d44038cf2c7838b0af781.png
[b463b1fa84aa4fbba0246bd8f36ef80c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ae9cc98aad68438aa603f39456e59434.png