??個人主頁： ?? 葉落閑庭
??我的專欄：??
c語言
數(shù)據(jù)結(jié)構(gòu)
javaEE
操作系統(tǒng)
Redis
石可破也，而不可奪堅；丹可磨也，而不可奪赤。
一、回文鏈表
1.1 題目描述
給你一個單鏈表的頭節(jié)點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。
1.2 思路分析
首先是要對該鏈表進(jìn)行非空校驗，若是空鏈表，直接返回fasle，否則，執(zhí)行其它邏輯，按照回文鏈表的規(guī)律，可以有這樣一個思路：若它是回文鏈表，可先找到他的前半個回文鏈表的最后一個節(jié)點，通過這個節(jié)點，就能找到開始回文的下半個鏈表的最后一個節(jié)點，從該節(jié)點處，將后半個回文鏈表進(jìn)行整體反轉(zhuǎn)，然后再定義指針進(jìn)行遍歷，從前半個回文鏈表的頭開始作為p1指針，后半個回文鏈表的頭作為p2指針，遍歷整個回文鏈表，判斷它們的值是否相同，若不相同，則不是回文鏈表，否則就是回文鏈表。
1.3 代碼演示
public boolean isPalindrome(ListNode head) {
//非空判斷
if (head == null) {
return false;
}
//找到回文鏈表前一段的最后一個節(jié)點
ListNode firstHalfEnd = endOfFirstList(head);
//找到回文鏈表反轉(zhuǎn)后的第一個節(jié)點
ListNode firstHaftStart = reverse(firstHalfEnd.next);
//設(shè)置標(biāo)記
boolean result = true;
//設(shè)置遍歷指針
ListNode p1 = head;
ListNode p2 = firstHalfStart;
while(result && p2 != null) {
if(p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
//恢復(fù)鏈表
firstHaftEnd.next = reverse(firstHalfEnd.next);
return result;
}
public static ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
public static ListNode endOfFirstList(ListNode head) {
//設(shè)置快慢指針進(jìn)行查找
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
二、環(huán)形鏈表
2.1 題目描述
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈>表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識鏈表的實際情況。
如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。
2.2 思路分析
先進(jìn)行非空校驗，若head為null，字直接返回false,否則進(jìn)行其它代碼，定義快慢指針slow和fast，fast指針比slow指針快走兩步，while循環(huán)進(jìn)行遍歷，條件是slow不等于fast，遍歷整個鏈表，循環(huán)內(nèi)是快慢指針的執(zhí)行，當(dāng)鏈表存在環(huán)時，fast指針總會多轉(zhuǎn)幾圈從而追上慢指針slow，此時兩個指針均指向同一個節(jié)點，表示該鏈表存在環(huán)，跳出循環(huán)，返回true,若是在循環(huán)中fast指向了空或者fast.next指向了空，表示該鏈表是正常的單向鏈表，直接返回false即可。
2.3 代碼演示
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head.next;
ListNode slow = head;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
//fast指針每次比slow指針快走兩步
//若該鏈表存在環(huán)，則這兩個指針會進(jìn)入環(huán)中
//fast總有機會比slow多轉(zhuǎn)n圈從而追上slow
//此時跳出循環(huán)，表示該鏈表是環(huán)形來鏈表
fast = fast.next.next;
slow = slow.next;
}
return true;
}
三、合并兩個有序鏈表
3.1 題目描述
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
文章來源：http://www.zghlxwxcb.cn/news/detail-722976.html
3.2 思路分析
按照題目要求，可以先對空值進(jìn)行校驗，若兩個鏈表均為空，則直接返回空，若只有一個鏈表為空，則直接返回另一個鏈表，否則進(jìn)行其它代碼，定義一個哨兵節(jié)點并定義一個指向它的的指針，當(dāng)兩個鏈表均不為空時，以此為條件開始遍歷，在循環(huán)中判斷兩個鏈表當(dāng)前的節(jié)點值的大小情況，若鏈表1的值小，則將哨兵位的下一個節(jié)點指向鏈表1，否則，則將哨兵位的下一個節(jié)點指向鏈表2，然后prev指向prev.next繼續(xù)遍歷鏈表，循環(huán)結(jié)束時，若鏈表長度不等，則較長的鏈表直接將剩余的節(jié)點加到prev的next下，返回合并后的鏈表的頭節(jié)點，即哨兵位的下一個節(jié)點。文章來源地址http://www.zghlxwxcb.cn/news/detail-722976.html
3.3 代碼演示
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null && list2 == null) {
return null;
}
if(list1 == null && list2 != null) {
return list2;
}
if(list1 != null && list2 == null) {
return list1;
}
//定義一個哨兵位節(jié)點
ListNode preHead = new ListNode(-1);
//定義一個指針指向哨兵位，作為遍歷指針
ListNode prev = preHead;
//當(dāng)鏈表都不為空時，開始遍歷
while(list1 != null && list2 != null) {
if(list1.val < list2.val) { //遍歷鏈表，比較鏈表當(dāng)前節(jié)點的值的大小
prev.next = list1; //若鏈表1的值小，則將哨兵位的下一個節(jié)點指向鏈表1
list1 = list1.next; //鏈表1繼續(xù)遍歷
} else {
prev.next = list2; //若鏈表2的值小，則將哨兵位的下一個節(jié)點指向鏈表2
list2 = list2.next; //鏈表2繼續(xù)遍歷
}
prev = prev.next; //prev繼續(xù)遍歷鏈表
}
prev.next = list1 == null ? list2 : list1; //若鏈表長度不等，則較長的鏈表直接將剩余的節(jié)點加到prev的next下即可
return preHead.next; //返回合并后的鏈表的頭節(jié)點，即哨兵位的下一個節(jié)點
}
到了這里，關(guān)于【力扣刷題】回文鏈表、環(huán)形鏈表、合并兩個有序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
