24. 兩兩交換鏈表中的節點

題目：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
講解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
復習可以先看視頻講解：（貼一張視頻講解的圖）

思想

• 搞清while()循環的終止條件，鏈表長度為奇數、偶數都記得考慮
• 交換兩個節點，需要定位到兩個節點之前的一個節點的位置

解題

/*** 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 swapPairs(ListNode head) {//先設置一個虛擬頭節點ListNode dummy=new ListNode(0,head);//讓cur指向兩個交換節點之前的節點ListNode cur=dummy;//當鏈表中元素個數為奇數時，cur.next.next==null為終止條件//當鏈表中元素個數為偶數時，cur.next==null為終止條件while(cur.next!=null&&cur.next.next!=null){//先暫存交換的第一個和兩個需要交換的元素的后一個元素（即1，2交換時,暫存節點1和3）ListNode temp=cur.next;ListNode temp1=cur.next.next.next;cur.next=cur.next.next;cur.next.next=temp;cur.next.next.next=temp1;//偏移curcur=temp;	//等價于cur = cur.next.next;}return dummy.next;}
}//參考答案，上面是我寫的，參考答案會比較清晰
// 將步驟 2,3 交換順序，這樣不用定義 temp 節點
public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {ListNode node1 = cur.next;// 第 1 個節點ListNode node2 = cur.next.next;// 第 2 個節點cur.next = node2; // 步驟 1node1.next = node2.next;// 步驟 3node2.next = node1;// 步驟 2cur = cur.next.next;}return dummy.next;
}

總結

和思想一樣嘍，主要在上面那張講解圖；

19. 刪除鏈表的倒數第 N 個結點

題目：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
文章講解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

思想

• 用一個快指針fastIndex和一個慢指針lowIndex，讓快指針先走n+1個位置，這樣便可以保證兩指針之間的間隔為n，然后同時移動兩指針直至fastIndex到達鏈表尾后，lowIndex的下一個位置即為要刪除的倒數第n個節點；

解題

/*** 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 dummy=new ListNode(0,head);ListNode fastIndex=dummy;ListNode slowIndex=dummy;//讓fastIndex先走n+1個位置，這樣fastIndex和slowIndex之間就間隔n個元素for(int i=0;i<=n;i++){fastIndex=fastIndex.next;}while(fastIndex!=null){fastIndex=fastIndex.next;slowIndex=slowIndex.next;}if(slowIndex.next.next==null){slowIndex.next=null;return dummy.next;}//slowIndex的下一個元素即為需要刪除的元素slowIndex.next=slowIndex.next.next;return dummy.next;}}////這是參考答案，更好理解，上面我自己寫的
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//新建一個虛擬頭節點指向headListNode dummyNode = new ListNode(0);dummyNode.next = head;//快慢指針指向虛擬頭節點ListNode fastIndex = dummyNode;ListNode slowIndex = dummyNode;// 只要快慢指針相差 n 個結點即可for (int i = 0; i <= n; i++) {fastIndex = fastIndex.next;}while (fastIndex != null) {fastIndex = fastIndex.next;slowIndex = slowIndex.next;}// 此時 slowIndex 的位置就是待刪除元素的前一個位置。// 具體情況可自己畫一個鏈表長度為 3 的圖來模擬代碼來理解// 檢查 slowIndex.next 是否為 null，以避免空指針異常if (slowIndex.next != null) {slowIndex.next = slowIndex.next.next;}return dummyNode.next;}
}

總結

記住思想的內容；

面試題 02.07. 鏈表相交

題目：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
文章講解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

思想

（1）方法一：

• 先計算出兩條鏈表的長度，讓鏈表A固定一直為長鏈表，計算兩鏈表長度差值，讓鏈表A先移動差值個單位，使A鏈表剩余長度和B鏈表相等，然后同時遍歷兩鏈表并比較對應節點是否相同；

（2）方法二：

解題

/*** 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 curA=headA;int sizeA=0;ListNode curB=headB;int sizeB=0;while(curA!=null){curA=curA.next;sizeA++;}while(curB!=null){curB=curB.next;sizeB++;}curA=headA;curB=headB;//讓curA始終指向長鏈表，curB指向短鏈表if(sizeA<sizeB){//交換curA和BListNode temp=curA;curA=curB;curB=temp;//交換長度int temp1=sizeA;sizeA=sizeB;sizeB=temp1;}int gap=sizeA-sizeB;while(gap-->0){curA=curA.next;}while(curA!=null){if(curA==curB){return curA;}curA=curA.next;curB=curB.next;}return null;}
}////這是參考答案，更好理解，上面我自己寫的
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求鏈表A的長度lenA++;curA = curA.next;}while (curB != null) { // 求鏈表B的長度lenB++;curB = curB.next;}curA = headA;curB = headB;// 讓curA為最長鏈表的頭，lenA為其長度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求長度差int gap = lenA - lenB;// 讓curA和curB在同一起點上（末尾位置對齊）while (gap-- > 0) {curA = curA.next;}// 遍歷curA 和 curB，遇到相同則直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}