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

这篇具有很好参考价值的文章主要介绍了【数据结构】单链表面试题讲解-＞贰。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌏引言

单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 ^_😀
【数据结构】单链表面试题讲解-＞贰,数据结构,数据结构,链表,java,合并链表,链表分割

🍀合并两个有序链表

🎄题目描述

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

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

🎋示例：

【数据结构】单链表面试题讲解-＞贰,数据结构,数据结构,链表,java,合并链表,链表分割

🎍解法思路

🚩建立虚拟节点

建立一个虚拟节点为newList；

建立虚拟节点的目的：

既然需要合并那么肯定是需要一个头节点
由于两个链表的头节点谁大谁小不知道，所以建立虚拟节点
小的就与虚拟节点相连
最后返回newList.next；

🚩tmp的建立

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

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

🚩进行合并

合并思想：

对list1与list2里的元素进行比较
谁小就与tmp连接，然后小的list向后走一步成为新的list1，tmp向后走一步成为新的tmp
依次类推进行比较
比如list1的值小，就将list1与tmp相连
然后list1与tmp各自向后走一步

结束条件：当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;
    }
}

🍀链表分割

🎄题目描述

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

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

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
    }
}

🎍示例：

【数据结构】单链表面试题讲解-＞贰,数据结构,数据结构,链表,java,合并链表,链表分割

🎋思路解析：

🚩链表拆分

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

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

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

🚩链表a的建立

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

建立过程：

对所需要分割的链表进行遍历
对每一个节点的元素大小进行判断，如果小于x就进入该链表
进入后对我们的a1进行判断，判断a1当前是否为null
如果为null，将当前的pHead赋给a1和a2；
如果不为null，将当前的pHead赋给a2.next，a2向后走一步

代码实现如下：

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;
    }
}