🌏引言
单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
🍀合并两个有序链表
🎄题目描述
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
🎋示例:
🎍解法思路
🚩建立虚拟节点
建立一个虚拟节点为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 } }
🎍示例:
🎋思路解析:
🚩链表拆分
将该链表拆分为两个链表;
- 链表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; } }
⭕总结
关于《【数据结构】单链表面试题讲解->贰》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!
文章知识点与官方知识档案匹配,可进一步学习相关知识