链表面试练习习题集（Java）
1.
思路：
因为杨辉三角是由二维数组构成，所以要先创建一个二维数组，如何用顺序表表示二维数组，可以通过List<List<Interger>>来表示一个二维数组，可以这样理解：先创建一个一维数组List，然后这个一维数组里面存放的元素类型是：<List<Integer>>，即接收整型的一维数组，所以一个一维数组中每个元素存的还是一维数组，那么就相当于二维数组了。
然后杨辉三角每行的第一列为1，则add（1）即可，中间为上一行对齐的两个元素之和，所以要先通过对二维数组get得到上一行的数组，再通过对上一行的数组get得到对齐的那两个元素，最后将和add到这一行的一维数组里，如此类推
最后每一行的最后一列元素也是1，因为add的底层实现是尾插，所以我们直接add（1）即可，最后再将这一行的一维数组add到二维数组里
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list=new ArrayList();//二维数组
List<Integer> list1=new ArrayList<>();//一维数组
list1.add(1);
list.add(list1);
for (int i = 1; i < numRows; i++) {
//第一列
List<Integer> curRow=new ArrayList<>();
curRow.add(1);
//中间
List<Integer> preRow=list.get(i-1);
for (int j = 1; j < i; j++) {
int a=preRow.get(j-1);
int b=preRow.get(j);
curRow.add(a+b);
}
//最后一列
curRow.add(1);
list.add(curRow);
}
return list;
}
}2.
思路：
看到求中间的东西，大概率会用到快慢指针，即当慢指针走一步，快指针走两步，当快指针到达终点时，慢指针刚好在中间，因为很简单的公式：路程=速度*时间；时间t相等，v快=2v慢，s=v快*t，v慢*t=1/2s
当结点为奇数个数时，刚好为中间的结点，当结点为偶数个数，为中间的第二个结点，根据快慢指针一个走两步，一个走一步，刚刚好都满足，所以就不用分类讨论了
什么时候停止指针移动呢，根据示例1和2，在示例1中，当快指针在5这里停止，在示例2中，当快指针在6的后面（即null）这里停止，所以循环条件为fast！=null&&fast.next！=null，注意&&前后两个条件不能换，必须先fast！=null再fast.next！=null，因为互换的话，当fast==null时，fast.next会报异常
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;//走一步
fast=fast.next.next;//走两步
}
return slow;
}
}3.
思路：
需要两个指针，一个记录当前结点cur，一个记录前面的那个结点precur，一开始都指向头结点head。如果cur的val等于传入的val，则先将cur往后移动一位，然后precur.next指向cur；否则precur走到cur的位置，cur往后移一步，循环条件为cur！=null，这是一般情况的代码
如果一开始头结点就等于val，即示例3的情况，那么按照上面的代码就不能将头结点移除，所以我们要判断一开始头结点是否为val，如果为val，则新头结点为头结点的后一个，因为移除完后的新头结点有可能仍然等于val，所以不是用if而是while，如果头结点为null，则说明全是val，如示例3的情况，此时就返回新头结点（也就是null）
一般都是先考虑正常情况，然后再来考虑特殊情况
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return head;
}
//解决一开始头结点的值就为val
while(head.val==val){
head=head.next;
if(head==null){
return head;
}
}
//说明此时头结点一定不为val
ListNode cur=head;//当前结点
ListNode precur=head;//前结点
while(cur!=null){
if(cur.val==val){
cur=cur.next;
precur.next=cur;
}else{
precur=cur;
cur=cur.next;
}
}
return head;
}
}4.
思路：
因为是反转，所以可以确定的是，第一个结点反转后一定是最后一个结点，所以我们要将头结点的next改为null，但改之前要记录头结点的下一个结点。然后采用每遍历一个结点就进行头插，即该结点cur的next指向头结点，但修改next的指向时，要先将原来的next指向的结点进行保存，保存到curN，然后头插完，cur=curN，循环条件为cur！=null
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return head;
}
//必要处理
ListNode cur=head.next;//第一步：记录头结点的next结点
head.next=null;//第二步：头结点的next改为null
//循环遍历，使用头插
while(cur!=null){
ListNode curN=cur.next;//循环中的第一步：记录下一个结点
cur.next=head;//第二步：当前结点头插到头结点之前
head=cur;//第三步：新的头结点为当前结点
cur=curN;//第四步：当前结点后移到原来的下一个结点位置
}
return head;
}
}5.
思路：
法一：可以利用我们刚刚上面那道题的代码，先将链表反转，再遍历第k个结点即可
法二：遍历两次，第一次求长度len，第二次遍历到第len-k个结点即可
法三：利用集合顺序表arraylist，遍历一次，用add将里面所有的元素放进顺序表里，然后再get（arraylist.size（）-k）即可
法四：快慢双指针，先提前让快指针走k步，然后慢指针和快指针以相同的速度每次走一步，当快指针走到最后时，慢指针的位置即为倒数第k个结点
示例代码（法一）
class Solution {
public int kthToLast(ListNode head, int k) {
if(head==null){
return -1;
}
//反转链表
ListNode cur=head.next;
head.next=null;
while(cur!=null){
ListNode curN=cur.next;
cur.next=head;
head=cur;
cur=curN;
}
//然后找
ListNode node=head;
for(int i=1;i<k;i++){
node=node.next;
}
return node.val;
}
}原文地址：https://blog.csdn.net/2301_80369371/article/details/140502549
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！