LinkedList和链表之刷题课(上)
在上一节,我们自己实现了一个单链表的结构,接下来我们来写几个面试题巩固一下
1. 删除链表中等于给定val的所有结点
解析题目:
如图,我们需要删除所有的值为12的结点
在head非空的情况下,我们删除一个结点,首先要找到这个结点,然后把这个结点的前面一个结点的next指向这个节点的下一个,这个就是总体的步骤,不过我们不止删除一个结点,我们需要删除所有是val值的结点,因此综上,我们需要俩个指针,prev和cur,prev指向的是删除结点的前一个结点,cur就是删除结点的当前节点,因此我们一开始先设置prev = head,cur = head.next;然后我们进入循环,如果当前的cur.val==key,我们就需要让prev.next = cur.next,然后我们需要跟新cur,cur = cur.next,如果我们当前节点的值不等于key,那么我们需要让prev = cur;cur=cur.next;
上面就大致解决了这个问题,但是我们还漏了一点,那就是head节点,head节点我们并没有判断它是否和val值一致.并且这行代码必须在删除完中间节点之后再删除,不然要用while,因为我们考虑到这种情况:1,1,1,2,2,1;我们如果一开始就删去1,那么第二个1是不可能被删除的,因为我们后期也没处理新的头结点的key,这一点同样也要在上一节博客修改一下.
整体代码:
public void removeAllKey(int key) {
//判断头节点是不是空的
if (this.head == null) {
return;
}
//判断头结点是不key
if (head.val == key) {
this.head = this.head.next;
}
ListNode prev = head;
ListNode cur = head.next;
//我们遍历除了head后面的元素
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
}2. 翻转一个单链表
解析题目:
我们翻转一个链表,也就是要把从最后一个节点开始,把它的next指向它的前一个
此时,我们可以采用头插法来,我们用cur记录当前节点,cur = head.next;然后我们需要把head.next置空,因为此刻head指向的节点是相当于我们翻转之后的最后一个节点.然后我们在把cur插到head前面的时候,我们需要用curNext来记录后面的节点,不然后续我们头插完,就找不然原先的链表了.然后我们需要跟新head,head = cur完成一轮插入,然后我们需要跟新cur,让cur指向curNext,再让curNext记录下一个节点.
还有个小地方,也就是我们如果链表head == null 或者head.next == null我们直接返回head即可,因为没有必要翻转.
整体代码:
//TODO 翻转链表
public ListNode reverseList() {
//判断链表是不是空的
if(head == null) {
return null;
}
//如果只有一个结点,就直接返回head即可
if(head.next == null){
return head;
}
//其他情况就用头插法
ListNode cur = head.next;
head.next = null;
while (cur != null) {
//把head置空
//记录下一个节点的位置
ListNode curNext = cur.next;
//把cur头插进去
cur.next = head;
//跟新head
head = cur;
//跟新cur
cur = curNext;
}
//返回head
return head;
}3. 给定一个带有头节点的非空单链表,返回链表的中间结点.如果有俩个中间结点,则返回第二个中间结点.
解析题目:
我们可以看见,我们返回中间结点,要分偶数个结点和奇数个结点.
我们先来看法1: 1> 求出整个链表的大小;2>找到len/2的结点
因为过于简单,我们这里就不画图了,直接解释代码:
先判断整个链表head是不是null;然后进入主题,求len,我们的循环条件是cur!=null,因为我们需要遍历所有的结点,如果用cur.next!=null;我们就会漏掉最后一个结点.然后注意,我们需要让cur重新指向head,因为cur刚刚在遍历的时候已经为null了;我们再设置一个计数变量i,中间长度mid,我们每次cur-cur.next;我们就需要对i进行++;
public ListNode middleNode() {
if(head==null){
return null;
}
//先求整个链表的长度
int len = 0;
ListNode cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
cur = head;
//再求长度/2找到这个中间节点
int mid = len / 2;
int i = 0;
while (i != mid) {
cur = cur.next;
i++;
}
return cur;
}法2 快慢指针,一开始fast和slow都指向head,然后fast走俩步,slow走一步;
这里因为奇偶数结点会分俩个情况,fast结束的标志会有俩种情况,也就是:fast == null和fast.next == null;在fast满足上面的情况之一就会说明slow到达了中间结点了.
这里我们解决俩个问题即可:
1> 为什么先判断fast再判断fast.next;
2> 为什么不能用||要用&&
整体代码:
public ListNode middleNodeFastAndSlow() {
if(head == null){
return null;
}
//我们定义俩个指针
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
//fast一次走俩步,slow一次走一步
fast = fast.next.next;
slow = slow.next;
}
return slow;
//俩个点
//1.为什么不能用||要用&& 因为如果是偶数个,最后我们fast会为null,因此判断fast.null会显示空指针异常
//2.为什么先要判断fast,再判断fast.next:因为如果是偶数个,fast最后会走到null,这时候先判断fast.next!=null会空指针异常
}4. 输入一个链表,输出该链表中倒数第k个结点
题目解析:
这个题目其实也有俩个方法,但是我们这里主要用快慢指针来解题
假设我们求的是倒数第k个结点,我们先让fast先走k-1步,然后我们再让fast和slow一起走,直到fast ==null为止;这个东西我是这么理解的,我们相当于把fast作为一个我们自定义的动态边界条件,让它先走k-1步,再同时走,这样fast肯定会先到最后一个结点,然后此时我们的slow所在位置就是倒数第k个结点.slow和fast相差k-1步.
然后我们这里要判断我们所要的结点的下标的合法性,此时我们我们可以优化一下k>size()这个条件,因为如果k很大,我们要遍历O(n),因为我们的fast要走k-1步,此时我们也需要一个循环,所以,我们直接去在这里面判断fast == null
整体代码:
//TODO 输出链表倒数第k个结点
//slow和fast总是差k-1
public ListNode FindtheToTail(int k) {
//先判断k的合法性
if(k < 0) {//我们可以优化一下这个k>siez()
return null;
}
//并且判断head是不是空
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
//fast走k-1步
for (int i = 0; i < k-1; i++) {
fast = fast.next;
//TODO 优化size()不去遍历,这个就是去处理k太大的情况
if(fast == null) {
return null;
}
}
//同时走
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
//fast到最后,slow的位置就是倒数第k个
return slow;
}5. 将俩个有序链表合并成一个新的有序链表并返回.
题目解析:
差不多是这么个情况,我们有俩个有序的链表,我们要把俩个合并成一个新的有序链表.我们先构造一个虚拟结点newH,然后我们再让list1和list2(此处,图上的head1就是list1,head2就是list2)互比较,小的就把该结点尾插到newH上去
具体步骤如图,我们要记录虚拟结点的位置,因此创建一个tmpH指向一开始的newH,我们把list1和list2的val进行比较,小的那一方,把该结点和newH连接在一起,如果是list1小,那么tmpH.next = list1;然后我们跟新list1,list=list.next;然后我们也要跟新newH,因为它指向的是链表的尾巴,我们进行尾插法,直到有一个链表为空为止
我们如图可以知道list2已经遍历完了,我们直接把list1剩下的元素连接过来即可,最后我们返回headH.next即可(因为headH是个虚拟结点)
整体代码:
//TODO 合并俩个有序列表
public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
//先生成一个开头的结点
MySingleList.ListNode newH = new MySingleList.ListNode(-1);
//tmpH始终指向的是链表的尾巴
MySingleList.ListNode tmpH = newH;
//判断俩个链表是不
while (list1 != null && list2 != null) {
//先比较list1和list2指向的结点,我们把小的值链接上
if(list1.val < list2.val) {
//小的话就把小的链接到newH上
tmpH.next = list1;
//跟新list1
list1 = list1.next;
} else {
//小的话就把小的链接到newH上
tmpH.next = list2;
//跟新list2
list2 = list2.next;
}
System.out.println("while末尾");
//tmpH始终指向的是链表的尾巴
tmpH = tmpH.next;
}
//如果其中一个为空了,那么就把另外一个链接过来即可
if(list1 != null) {
tmpH.next = list1;
}
if (list2 !=null){
tmpH.next = list2;
}
return newH.next;
}