?刷題計(jì)劃day4繼續(xù)，可以點(diǎn)個(gè)免費(fèi)的贊哦~

下一期將會(huì)開啟哈希表刷題專題，往期可看專欄，關(guān)注不迷路，

您的支持是我的最大動(dòng)力🌹~

目錄

?刷題計(jì)劃day4繼續(xù)，可以點(diǎn)個(gè)免費(fèi)的贊哦~

下一期將會(huì)開啟哈希表刷題專題，往期可看專欄，關(guān)注不迷路，

您的支持是我的最大動(dòng)力🌹~

題目一：19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

法一：計(jì)算鏈表長度

法二：雙指針

題目二：面試題 02.07. 鏈表相交

法一：雙指針

法二：合并鏈表實(shí)現(xiàn)同步移動(dòng)

題目三：142. 環(huán)形鏈表 II

法一：快慢指針法

1.判斷鏈表是否有環(huán)

2.如果有環(huán)，如何找到環(huán)的入口

2.1 n==1

2.2 n>1

法二：哈希表

---

題目一：19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

leetcode:19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

(https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)

法一：計(jì)算鏈表長度

常規(guī)思路：先遍歷得到鏈表長度L，然后再次遍歷到 L-n+1個(gè)結(jié)點(diǎn)，便是我們需要?jiǎng)h除的結(jié)點(diǎn)；

這里我們還是使用虛擬頭結(jié)點(diǎn)統(tǒng)一，于是從虛擬結(jié)點(diǎn)開始遍歷L-n+1個(gè)結(jié)點(diǎn)，它的下一個(gè)結(jié)點(diǎn)便是我們要?jiǎng)h除的結(jié)點(diǎn)，這樣我們只需修改一次指針，就可完成刪除操作。

如圖輔助理解：

AC代碼

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead = new ListNode();dummyHead.next=head;ListNode cur = dummyHead;int length = getLength(head);for (int i=1;i<length-n+1;i++){cur = cur.next;}if(cur.next!=null){//避免空指針cur.next = cur.next.next;//刪除操作}return dummyHead.next;
?}public int getLength(ListNode head){int length = 0;while(head != null){length++;head=head.next;}return length;}
}

法二：雙指針

主要思路：

要?jiǎng)h除倒數(shù)第n個(gè)，我們可以使用雙指針，這樣不用去求長度；

保持一個(gè)相差n的區(qū)間，fast在前,slow在后。這樣等fast走到鏈表末尾，slow對應(yīng)的就是我們要?jiǎng)h除的結(jié)點(diǎn)；

因?yàn)殒湵韯h除我們需要通過前一個(gè)結(jié)點(diǎn)，所以將相差區(qū)間設(shè)為n+1，可以結(jié)合圖理解：

AC代碼

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead = new ListNode();dummyHead.next=head;ListNode fast = dummyHead;ListNode slow = dummyHead;
?// 只要快慢指針相差 n 個(gè)結(jié)點(diǎn)即可for (int i=1;i<=n+1;i++){fast = fast.next;}while (fast!=null){fast = fast.next;slow = slow.next;}
?if(slow.next!=null){slow.next = slow.next.next;}return dummyHead.next;}
}

題目二：面試題 02.07. 鏈表相交

leetcode：面試題 02.07. 鏈表相交

(https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/)

簡單來說，就是求兩個(gè)鏈表交點(diǎn)節(jié)點(diǎn)的指針。 這里要注意，交點(diǎn)不是數(shù)值相等，而是指針相等。

為了方便舉例，假設(shè)節(jié)點(diǎn)元素?cái)?shù)值相等，則節(jié)點(diǎn)指針相等。

看如下兩個(gè)鏈表，目前curA指向鏈表A的頭結(jié)點(diǎn)，curB指向鏈表B的頭結(jié)點(diǎn)：

我們求出兩個(gè)鏈表的長度，并求出兩個(gè)鏈表長度的差值，然后讓curA移動(dòng)到，和curB 末尾對齊的位置，如圖

此時(shí)我們就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB，則找到交點(diǎn)。

否則循環(huán)退出返回空指針。

AC代碼

法一：雙指針

public class Solution {
?public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 初始化兩個(gè)鏈表的當(dāng)前節(jié)點(diǎn)ListNode cur1 = headA;ListNode cur2 = headB;// 初始化兩個(gè)鏈表的長度int len1 = 0;int len2 = 0;
?// 求cur1長度while (cur1 != null) {len1++;cur1 = cur1.next;}// 求cur2長度while (cur2 != null) {len2++;cur2 = cur2.next;}
?// 重新初始化兩個(gè)鏈表的當(dāng)前節(jié)點(diǎn)cur1 = headA;cur2 = headB;
?// 如果第一個(gè)鏈表比第二個(gè)短，交換兩個(gè)鏈表的頭節(jié)點(diǎn)和長度if (len1 < len2) {//1. swap (len1, len2);int temp = len1;len1 = len2;len2 = temp;//2. swap (cur1, cur2);ListNode temNode = cur1;cur1 = cur2;cur2 = temNode;}
?// 計(jì)算長度的差值int gap = len1 - len2;// 移動(dòng)較長鏈表的當(dāng)前節(jié)點(diǎn)，使cur1與cur2的末尾位置對齊，看圖while (gap-- > 0) {cur1 = cur1.next;}
?// 同時(shí)遍歷兩個(gè)鏈表，遇到相同則直接返回while (cur1 != null) {if (cur1 == cur2) {return cur1; // 返回相交的節(jié)點(diǎn)}cur1 = cur1.next;cur2 = cur2.next;}
?// 如果兩個(gè)鏈表沒有相交，返回nullreturn null;}
}

法二：合并鏈表實(shí)現(xiàn)同步移動(dòng)

主要思路：

1. 同步移動(dòng)指針：

   • 使用一個(gè) while 循環(huán)，只要 p1 和 p2 沒有相遇，就繼續(xù)移動(dòng)指針。

   • 對于 p1，如果它到達(dá)了鏈表 A 的末尾（即 p1 為 null），則將它移動(dòng)到鏈表 B 的頭部，重新開始遍歷。

   • 對于 p2，如果它到達(dá)了鏈表 B 的末尾（即 p2 為 null），則將它移動(dòng)到鏈表 A 的頭部，重新開始遍歷。

2. 相遇即相交：

   • 當(dāng)兩個(gè)指針 p1 和 p2 相遇時(shí)，它們指向的就是鏈表相交的節(jié)點(diǎn)。因?yàn)閮蓚€(gè)指針最終都會(huì)遍歷完兩個(gè)鏈表，如果鏈表有相交點(diǎn)，它們最終會(huì)在相交點(diǎn)相遇。

3. 返回結(jié)果：

   • 一旦 p1 和 p2 相遇，即它們指向同一個(gè)節(jié)點(diǎn)，就返回這個(gè)節(jié)點(diǎn)。

 public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// p1 指向 A 鏈表頭結(jié)點(diǎn)，p2 指向 B 鏈表頭結(jié)點(diǎn)ListNode p1 = headA, p2 = headB;while (p1 != p2) {// p1 走一步，如果走到 A 鏈表末尾，轉(zhuǎn)到 B 鏈表if (p1 == null) p1 = headB;else ? ? ? ? ?  p1 = p1.next;// p2 走一步，如果走到 B 鏈表末尾，轉(zhuǎn)到 A 鏈表if (p2 == null) p2 = headA;else ? ? ? ? ?  p2 = p2.next;}return p1;}
}

題目三：142. 環(huán)形鏈表 II

leetcode：142. 環(huán)形鏈表 II

(https://leetcode.cn/problems/linked-list-cycle-ii/description/)

法一：快慢指針法

判斷鏈表是否有環(huán)，我們一般可以使用快慢指針法

此題還是有一定難度，考察了對鏈表環(huán)的判斷，已經(jīng)需要進(jìn)行數(shù)學(xué)運(yùn)算，下文會(huì)進(jìn)行詳細(xì)解釋。

對于此題大致分為兩大步：

1.判斷鏈表是否有環(huán)

2.如果有環(huán)，如何找到環(huán)的入口

---

1.判斷鏈表是否有環(huán)

分別定義fast,slow指針，fast指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)，slow指針每次移動(dòng)一個(gè)節(jié)點(diǎn)，如果 fast 和 slow指針在途中相遇 ，說明這個(gè)鏈表有環(huán)。

2.如果有環(huán)，如何找到環(huán)的入口

這步已經(jīng)可以判斷鏈表是否有環(huán)了，接下來是尋找環(huán)的入口，需要用到一點(diǎn)數(shù)學(xué)運(yùn)算。

假設(shè)從頭結(jié)點(diǎn)到環(huán)形入口節(jié)點(diǎn) 的節(jié)點(diǎn)數(shù)為x。 環(huán)形入口節(jié)點(diǎn)到 fast指針與slow指針相遇節(jié)點(diǎn) 節(jié)點(diǎn)數(shù)為y。 從相遇節(jié)點(diǎn) 再到環(huán)形入口節(jié)點(diǎn)節(jié)點(diǎn)數(shù)為 z。 如圖所示：

那么當(dāng)相遇時(shí)：

slow指針走過的節(jié)點(diǎn)數(shù)為: x + y， fast指針走過的節(jié)點(diǎn)數(shù)：x + y + n (y + z)，n為fast指針在環(huán)內(nèi)走了n圈才遇到slow指針， （y+z）為 一圈內(nèi)節(jié)點(diǎn)的個(gè)數(shù)A。

加深理解注：

1.fast指針為什么 n (y + z)？ 因?yàn)閒ast比slow快，fast進(jìn)入圈后至少需要一圈后追反超slow，由此也可知道，n>=1（后續(xù)解題會(huì)用）。

2.為什么slow就不用比如k(y+z)？ 因?yàn)閟low進(jìn)入圈后在一圈內(nèi)一定會(huì)被fast追上

3.那為什么slow一圈內(nèi)就一定會(huì)被fast追上呢？ 可以這樣通俗理解：首先fast會(huì)比slow快1，如果slow走一圈，fast就會(huì)走兩圈，那一定會(huì)追上。

因?yàn)閒ast指針是一步走兩個(gè)節(jié)點(diǎn)，slow指針一步走一個(gè)節(jié)點(diǎn)， 所以 slow指針走過的節(jié)點(diǎn)數(shù) * 2 = fast指針走過的節(jié)點(diǎn)數(shù)，所以可以列出方程：

(x + y) * 2 = x + y + n (y + z)

因?yàn)槲覀円噎h(huán)形入口，即需要找x，將x單獨(dú)放出來化簡：

x = n (y + z) - y

但是我們看一下這個(gè)式子呢，也發(fā)現(xiàn)不了什么，我們是想通過右邊的參數(shù)來求x，但發(fā)現(xiàn)目前右側(cè)也沒啥特殊形式，還有個(gè)-y。于是我們可以提一個(gè)(y+z)出來，

x = (n - 1) (y + z) + z(此處n>=1，前面有解釋)

此時(shí)就明了了。

---

2.1 n==1

當(dāng) n為1的時(shí)候，公式就化解為 x = z，

這就意味著，從頭結(jié)點(diǎn)出發(fā)一個(gè)指針，從相遇節(jié)點(diǎn)也出發(fā)一個(gè)指針，這兩個(gè)指針每次只走一個(gè)節(jié)點(diǎn)， 那么當(dāng)這兩個(gè)指針相遇的時(shí)候就是 環(huán)形入口的節(jié)點(diǎn)。

也就是在相遇節(jié)點(diǎn)處，定義一個(gè)指針index1，在頭結(jié)點(diǎn)處定一個(gè)指針index2。

讓index1和index2同時(shí)移動(dòng)，每次移動(dòng)一個(gè)節(jié)點(diǎn)， 那么他們相遇的地方就是 環(huán)形入口的節(jié)點(diǎn)。

2.2 n>1

那么 n如果大于1是什么情況呢，就是fast指針在環(huán)形轉(zhuǎn)n圈之后才遇到 slow指針。

其實(shí)這種情況和n為1的時(shí)候效果是一樣的，一樣可以通過這個(gè)方法找到 環(huán)形的入口節(jié)點(diǎn)，只不過，index1 指針在環(huán)里 多轉(zhuǎn)了(n-1)圈，然后再遇到index2，相遇點(diǎn)依然是環(huán)形的入口節(jié)點(diǎn)。

代碼如下：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;
?//相遇,有環(huán)if(fast==slow){ListNode index1  = fast;ListNode index2  = head;// 兩個(gè)指針，從頭結(jié)點(diǎn)和相遇結(jié)點(diǎn)，各走一步，直到相遇，相遇點(diǎn)即為環(huán)入口while (index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}
?}return null;}
}

法二：哈希表

這個(gè)思路就簡單很多，時(shí)間復(fù)雜度：O(N)，空間復(fù)雜度：O(N)；

但第一種雙指針的解法也需要掌握，時(shí)間復(fù)雜度：O(N)，空間復(fù)雜度：O(1)。

關(guān)于哈希表我們下期也會(huì)做相應(yīng)的專題刷題。

主要思路：遍歷鏈表中的每個(gè)節(jié)點(diǎn)，并將它記錄下來；一旦遇到了此前遍歷過的節(jié)點(diǎn)，就可以判定鏈表中存在環(huán)。借助哈希表可以很方便地實(shí)現(xiàn)。

代碼：

詳細(xì)見注解

public class Solution {public ListNode detectCycle(ListNode head) {// 初始化指針pos指向頭結(jié)點(diǎn)ListNode pos = head;// 使用HashSet來存儲(chǔ)已經(jīng)訪問過的節(jié)點(diǎn)Set<ListNode> visited = new HashSet<ListNode>();
?// 遍歷鏈表while (pos != null) {// 如果當(dāng)前節(jié)點(diǎn)已經(jīng)被訪問過，說明存在環(huán)，返回當(dāng)前節(jié)點(diǎn)if (visited.contains(pos)) {return pos;} else {// 否則，將當(dāng)前節(jié)點(diǎn)添加到visited集合中visited.add(pos);}// 移動(dòng)到下一個(gè)節(jié)點(diǎn)pos = pos.next;}
?// 如果遍歷完整個(gè)鏈表都沒有發(fā)現(xiàn)環(huán)，返回nullreturn null;}
}