Java 链表
K稳重 人气:0前言：
上一章更到了链表，虽然知道了什么是链表，链表的结构是怎么样的，但这是远远不够的，我们只清楚了点皮毛，如果让你做题你还是会无从下手，所以我们必须多做题，在做题的过程中慢慢的我们就会觉得一切都很简单。下面我们就来做几道经典的链表面试题！！！！！！
第一题
题目：反转一个单链表
每个节点是不变的，只是修改当前每个节点的指向
看图分析：
问题分析：
每个节点是不变的，只需要修改当前每个节点的指向，第一个节点指向变成null，第二个节点的指向是第一个节点。
问题讲解：
我们需要定义四个节点变量
head变量等于头节点
cur = head
prev = null
curNext = cur.next
第一步：curNext = cur.next
第二步：cur.next = prev
第三步：prev = cur
第四步：cur = curNext
我们看一下图解是如何走的
第一步：curNext = cur.next
第二步：cur.next = prev
第三步： prev = cur
第四步： cur = curNext
这四步让它是一个循环，我们再走一个循环给大家看
第五步： curNext = cur.next
第六步： cur.next = prev
第七步： prev = cur
第八步： cur = curNext
这样两个循环下来我想大家看的就很明白了，那既然是循环肯定会有终止条件，所以我们可以看一下，当cur走到最后一个字节的时候，我们仍然需要 cur.next = prev，再往后走的话cur就为null了，为null的时候就反转结束了。所以我们循环的终止条件就是cur != null。另外我们还需要判断一直指向头节点的head为不为null，如果为null的话就是没有这个链表，直接返回null就可以了。反转完成后最后一个节点就变成了头节点，所以我们返回prev就可以了、那我们就可以来写代码了。
代码实现：
lass Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head;
ListNode prev = null;
while (cur != null) {
ListNode cutNext = cur.next;
cur.next = prev;
prev = cur;
cur = cutNext;
}
return prev;
}
}力扣
https://leetcode-cn.com/problems/reverse-linked-list/description/
题目链接在上面，大家一定打开链接自己做一下。
第二题
题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
画图分析：
问题分析：奇数的话返回中间的节点，偶数的话返回第二个中间节点，也就是说偶数返回第三个。
问题讲解：
同样的，我们来定义两个引用变量
fast，slow两个引用变量都等于head头节点
如图：
我们让fast一次走两步，slow一次走两步，奇数情况：fast.next为null，slow所在的就是中间节点位置 。偶数情况：fast为null，low所在的就是中间节点位置 。原因是为什么呢？两个同时走，fast的速度是slow的两倍，那么路程也是两倍，一个走到终点了，那么另一个就是走了路程的一半。有这样的思路我们就可以来写代码了 ，同样的先要判断一下链表是不是为null，为null直接返回null就好了
代码实现：
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null ){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}力扣
https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
第三题
题目：输入一个链表，输出该链表中倒数第k个结点
画图分析：
问题讲解：
同样的，我们来定义两个引用变量
fast，slow两个引用变量都指向头节点
如图：
如果我们要找倒数第K个，从第K个到倒数第1个需要走K-1步，所以我们先让fast走K-1步，当走完K-1步，fast指向的是倒数第一个时候，那么slow就是我们要找的倒数第K给，如果fast走完K-1步，fast指向的不是倒数第一个，那么这个时候我们让fast和slow一起往后走，他们始终差了K-1步，当fast 走到倒数第一个的时候，这个时候slow所指向的节点就是我们要找的倒数第K个。这里K我们也要判断一下，如果K<=0 或者 k>链表的长度，我们直接返回null就可以了。
代码实现：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k-1 != 0){
fast = fast.next;
if(fast == null){
return null;
}
k--;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}第四题
题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
画图分析：这是我们的两个链表
问题讲解：
同样的，先定义两个引用变量headA和headB分别指向两个链表的头节点。
定义一个虚拟节点，假设叫newHead，在定义一个引用变量tmp等于newHead
首先我们先来比较headA和headB的大小，如果headA.val<headB.val,那么就让tmp.next等于headA
因为12小，那么就让headA = headA.next，如果后面再找到比12大数字就要放在12的后头，所以我们让tmp = tmp.next，
这个时候再比较headA和headB, 如果headA.val>headB.val,那么就是让tmp.next = headB，再让headB = headB.next，tmp = tmp.next
这样就构成了我们的一个循环，当headA和headB都不为null的时候我们才能继续循环，当循环结束，要么headA为null，要么headB为null，当headA为null，我们让tmp.next = headB,当headB为null，我们让tmp.next = headA,
代码实现：
lass Solution {
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newhead = new ListNode(-1);
ListNode tmp = newhead;
while (headA != null && headB != null) {
if (headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
} else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA == null){
tmp.next = headB;
}
if(headB == null){
tmp.next = headA;
}
return newhead.next;
}
}力扣
https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
因为时间原因：今天就先打卡这4道面试题，这4道面试题都是比较经典的面试题，对我们链表这块的学习会很有帮助。学习数据结构就是要多刷题，这样你才能完全掌握数据结构这门知识。今天太晚了，明天再继续给大家更面试题吧。有任何疑问大家都可以私信我，有问题欢迎大家指出来，我都会虚心学习的，希望可以和大家一起进步。
加载全部内容