劍指Offer之Java算法習題精講鏈表專項訓練
更新時間：2022年03月22日 11:03:45 作者：明天一定.
跟著思路走，之后從簡單題入手，反復去看，做過之后可能會忘記，之后再做一次，記不住就反復做，反復尋求思路和規(guī)律，慢慢積累就會發(fā)現(xiàn)質的變化
題目一
鏈表題——鏈表合并
根據(jù)給定的兩個升序鏈表合并為一個新的升序鏈表
具體題目如下
解法
/**
* 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 a = new ListNode(0),b = a;
while(list1!=null&&list2!=null){
if(list1.val<=list2.val){
a.next = list1;
list1 = list1.next;
}else{
a.next = list2;
list2 = list2.next;
}
a = a.next;
}
if(list1==null){
a.next = list2;
}
if(list2==null){
a.next = list1;
}
return b.next;
}
}
?題目二
鏈表題——查找鏈表
根據(jù)給定的鏈表頭文件判斷其中是否有環(huán)
具體題目如下
?解法一
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(!set.add(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
解法二
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null){
if(fast.next==null) return false;
slow = slow.next;
fast = fast.next.next;
if(fast==slow) return true;
}
return false;
}
}
題目三
鏈表題——查找數(shù)組中元素位置
根據(jù)給定的鏈表頭節(jié)點查找返回鏈表入環(huán)的第一個節(jié)點
具體題目如下
?解法一
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(!set.add(head)){
return head;
}
set.add(head);
head = head.next;
}
return null;
}
}
解法二
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null){
if(fast.next==null) return null;
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
slow = head;
break;
}
}
while(fast!=null){
if(slow == fast){
return slow;
}
slow = slow.next;
fast = fast.next;
}
return null;
}
}
題目四
鏈表題——查找鏈表相交起始節(jié)點
根據(jù)給定的兩個鏈表頭節(jié)點按照指定條件查找起始節(jié)點
具體題目如下
解法一
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(headA!=null){
set.add(headA);
headA = headA.next;
}
while(headB!=null){
if(!set.add(headB)){
return headB;
}
set.add(headB);
headB = headB.next;
}
return null;
}
}
解法二
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while(a != b){
if(a == null) a = headB;
else a = a.next;
if(b == null) b = headA;
else b = b.next;
}
return a;
}
}
題目五
鏈表題——鏈表操作
根據(jù)給定的鏈表刪除指定節(jié)點并返回頭節(jié)點
具體題目如下
?解法
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode x = findFromEnd(node,n+1);
x.next = x.next.next;
return node.next;
}
private ListNode findFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0;i<k;i++){
fast = fast.next;
}
while(fast!=null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
題目六
鏈表題——查找鏈表中間節(jié)點
根據(jù)給定的鏈表頭節(jié)點查找其中間節(jié)點
具體題目如下
?解法
/**
* 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) {
ListNode fast = head ;
ListNode slow = head ;
while(fast!=null){
if(fast.next == null) return slow;
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
到此這篇關于劍指Offer之Java算法習題精講鏈表專項訓練的文章就介紹到這了,更多相關Java 鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Spring Cloud Gateway + Nacos 實現(xiàn)動態(tài)路由
這篇文章主要介紹了Spring Cloud Gateway + Nacos 實現(xiàn)動態(tài)路由的方法，幫助大家實現(xiàn)路由信息的自動更新，感興趣的朋友可以了解下2020-10-10
深入理解 Java、Kotlin、Go 的線程和協(xié)程
這篇文章主要介紹了深入理解 Java、Kotlin、Go 的線程和協(xié)程,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
解決Error:(1,?1)?java:?非法字符:?'\ufeff'問題
這篇文章主要介紹了解決Error:(1,?1)?java:?非法字符:?'\ufeff'問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要介紹了java加密算法--MD5加密和哈希散列帶秘鑰加密算法源碼的相關資料,這里附實例代碼，幫助到大家學習理解，需要的朋友可以參考下2016-11-11
這篇文章主要介紹了Mybatis 緩存原理及失效情況解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
這篇文章主要為大家介紹了AgileBoot?項目內統(tǒng)一的錯誤碼設計分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-10-10
Spring Cloud 是一套完整的微服務解決方案，基于 Spring Boot 框架，準確的說，它不是一個框架，而是一個大的容器，它將市面上較好的微服務框架集成進來，從而簡化了開發(fā)者的代碼量,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Java如何導出zip壓縮文件問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
這篇文章主要介紹了關于fastjson的常見API詳解,Fastjson是一個Java庫，可用于將Java對象轉換為其JSON表示,它還可用于將JSON字符串轉換為等效的Java對象,Fastjson可以處理任意Java對象，包括您沒有源代碼的預先存在的對象,需要的朋友可以參考下2023-07-07
下面小編就為大家?guī)硪黄P于多線程常用方法以及對鎖的控制(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05