Java链表必会面试题01

前面已经学习了有关链表的基础知识有三个要点需要牢记cur cur.next; while(cur ! null) while(cur.next ! null)注意课上写出的代码课下也需要独立完成目录一、来看第一题反转链表二、链表的中间节点三、有关 节点静态内部类 的一些解释四、输⼊⼀个链表输出该链表中倒数第k个结点五、将两个有序链表合并为⼀个新的有序链表并返回。六、链表的回⽂结构一、来看第一题反转链表OJ链接https://leetcode.cn/problems/reverse-linked-list/description/来看思路要改变链表的结构这里建议写代码需要 画图思路调试先完成再完美先想到啥写啥/** * 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 reverseList(ListNode head) { } }在这个模版下开始思考首先考虑特殊情况/** * 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 reverseList(ListNode head) { //1.判断链表是不是空的 if (head null) { return null; } //2. 判断是不是只有1个节点 if (head.next null) { return head; } //3. 说明至少有2个节点及其以上 } }后面的思路也就是先隔离一个头节点出来再利用 头插法 不断将后续的节点 插入到 这个头节点的前面如图所示循环外部开头--核心代码cur 代表需要 翻转的 节点cur head.next; head.next null;那么开头的准备工作完成后考虑循环循环条件while(cur ! null)循环内部while (cur ! null) { ListNode curN cur.next; // 这2行代码在进行头插 cur.next head; head cur; cur curN; }所以总结的代码为public ListNode reverseList(ListNode head) { //1.判断链表是不是空的 if(head null) { return null; } //2. 判断是不是只有1个节点 if(head.next null) { return head; } //3. 说明至少有2个节点及其以上 ListNode cur head.next; head.next null; while(cur ! null) { ListNode curN cur.next; //这2行代码在进行头插 cur.next head; head cur; // cur curN; } return head; }二、链表的中间节点给定⼀个带有头结点head的非空单链表返回链表的中间结点。如果有两个中间结点则返回第 二个中间结点。OJhttps://leetcode.cn/problems/middle-of-the-linked-list/description//** * 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 middleNode(ListNode head) { } }如上图所示即为解题思路我们最容易想到从头节点出发移动 len/2 count 个位置即可找到中间的节点这个思想比较容易想到。但是假如我只让你 便利一遍呢那就要介绍--快慢指针法了也就是 始终让 fast这个引用 走的位置 每次都比 slow这个引用 走的位置 多一倍当 fast.next null(链表有奇数个节点时) fast null(链表有偶数个节点时)将跳出循环class Solution { public ListNode middleNode(ListNode head) { ListNode fast head; ListNode slow head; while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; } return slow; } }这里提醒一下这个循环条件不能够写成while (fast.next ! null fast ! null)这样极其有可能报 空指针异常当链表的元素个数为 偶数个 时三、有关 节点静态内部类 的一些解释四、输⼊⼀个链表输出该链表中倒数第k个结点OJ链接https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description//** * 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 int kthToLast(ListNode head, int k) { } }第一个思路让开头的 节点引用head 移动 size()-k 个位置但是假如只能够 遍历一遍 呢class Solution { public int kthToLast(ListNode head, int k) { //1.判断k的值的合法性 if(k 0 || head null) { return -1; } //2.先让fast走K-1步 ListNode fast head; ListNode slow head; int count 0; while (count ! k-1) { fast fast.next; if(fast null) { return -1; } count; } //3.开始同时出发 while (fast.next ! null) { fast fast.next; slow slow.next; } return slow.val; } }五、将两个有序链表合并为⼀个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJhttps://leetcode.cn/problems/merge-two-sorted-lists/description/解题模板/** * 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 headA, ListNode headB) { } }还是老样子先画图 来理解以下思路结合图片思路大概是先给一个傀儡节点作为头节点进行进行操作再加上一个tmp的操作结点详细代码为/** * 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 headA, ListNode headB) { ListNode newH new ListNode(-1); ListNode tmp newH; while(headA ! null headB ! null) { if(headA.val headB.val) { tmp.next headA; tmp headA; headA headA.next; } else { tmp.next headB; tmp headB; headB headB.next; } } if(headA ! null) { tmp.next headA; } if(headB ! null) { tmp.next headB; } return newH.next; } }其中注意最先来考虑一些特殊情况由于上述代码已经可以考虑下面的情况了所以就可以省略了。if(headA ! null headB null) { return headA; } if(headA null headB ! null) { return headB; } if(headA null headB null) { return null; }六、链表的回⽂结构OJhttps://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-rankingimport java.util.*; /* public class ListNode { int val; ListNode next null; ListNode(int val) { this.val val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode A) { // write code here } }结合图片解题思路为1. 找到中间节点2. 翻转中间节点 之后的节点3. 一个往前 一个往后 直到相遇1. val值一样2. 两个没有相遇import java.util.*; /* public class ListNode { int val; ListNode next null; ListNode(int val) { this.val val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode head) { // write code here if(head null){ return true; } //1.找中间节点 ListNode fast head; ListNode slow head; while(fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; } //2.slow此时指向了中间位置 开始翻转后半部分 ListNode cur slow.next; while(cur ! null) { ListNode curN cur.next; cur.next slow; slow cur; cur curN; } //3. 此时head和cur一直走 直到相遇 while(head ! slow) { if(head.val ! slow.val) { return false; } //判断偶数的情况 if(head.next slow){ return true; } head head.next; slow slow.next; } return true; } }