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

第一遍-遞歸-小看了一下題解

• 思路：
  • 讀了兩遍題目才理解…
  • 相鄰節點的交換，這個操作很容易實現，但需要一個tmpNode
  • 因為是鏈表的題目，沒開始思考之前先加了dummyNode，還真管用
  • 把dummyNode作為了最后返回用的，以及新增preNode作為tmpNode
  • 用遞歸寫是因為不想用循環了…感覺遞歸寫起來好玩一些
  • 小看了一下題解的地方：（其實再給自己多一些debug的次數應該也能試出來）
    • 遞歸結束條件：|| i.next.next == null這個沒有想出來

/*
* 這部分是自己在Idea上寫的，用了之前的題目實現的MyLinkedList
* 感覺這樣會比在力扣上面寫更能熟悉鏈表一些，而且debug更容易一些
* */
package LinkList;public class Linklist_test {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtHead(4);myLinkedList.addAtHead(3);myLinkedList.addAtHead(2);myLinkedList.addAtHead(1);LinklistSolution solution = new LinklistSolution();ListNode head = solution.swapPairs(myLinkedList.dummy.next);for (; head != null; head = head.next) {System.out.println(head.val);}}
}class LinklistSolution {public ListNode reverseDouble(ListNode head, ListNode preNode, ListNode i, ListNode j) {// 交換節點preNode.next = i.next;i.next = j.next;j.next = i;if (i.next == null || i.next.next == null) return head.next;// 移動節點j = i.next.next;i = i.next;preNode = preNode.next.next;return reverseDouble(head, preNode, i, j);}public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode dummy = new ListNode(-1);dummy.next = head;ListNode preNode = dummy;ListNode i = head;ListNode j = head.next;return reverseDouble(dummy, preNode, i, j);}
}

• 看了一下代碼隨想錄Java的遞歸題解，嗯，真🐂，我想不出來
  • 示例代碼很好的利用了鏈表是通過指向下一個節點的地址鏈接的，所以返回newNode可以實現；

// 示例代碼
class LinklistSolution {public ListNode swapPairs(ListNode head) {// base case 退出提交if(head == null || head.next == null) return head;// 獲取當前節點的下一個節點ListNode next = head.next;// 進行遞歸ListNode newNode = swapPairs(next.next);// 這里進行交換next.next = head;head.next = newNode;return next;}
}

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

第一遍

• 思路：
  • 這一題誤操作了，忘記先自己想了，直接看題解了…
  • 算是兩遍AC吧，第一次fast指針的循環沒控制好

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);dummy.next = head;if (head.next == null) {return head.next;}ListNode slow = dummy;ListNode fast = dummy;for (int i = 0; i <= n; i++) {fast = fast.next;}for (; fast != null; fast = fast.next) {slow = slow.next;// fast = fast.next; 第一次提交的時候多寫了一個這個，debug的時候才發現不對}slow.next = slow.next.next;return dummy.next;}
}

面試題 02.07. 鏈表相交

第一遍

• 思路：
  • 讀了第一遍直接寫了，第一次開始寫循環又出錯了…而且出了兩個錯誤
    • 錯誤1：判斷條件寫成了A.next != null，導致所有的鏈表長度都-1，長度為1且相交的時候會有問題；
    • 錯誤2：沒有寫A = A.next的修改條件；
  • 第一遍寫完，使用的是A.val = B.val的判斷條件，不對，發現有val相等，但是答案并不是對應指針；
  • 麻了，又去看題，看了n遍都沒看懂；
  • 最后看了題解，結果發現是指針相等（怎么從題中讀出的指針相等的？）

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode A = headA;ListNode B = headB;int lenA = 0, lenB = 0;while (A != null) {lenA++;A = A.next;}while (B != null) {lenB++;B = B.next;}A = headA;B = headB;int n = lenA >= lenB ? lenA - lenB : lenB - lenA;int m = lenA >= lenB ? lenB : lenA;if (lenA > lenB) {while (n > 0) {A = A.next;n--;}} else {while (n > 0) {B = B.next;n--;}}while (m > 0) {if (A == B) {return A;}A = A.next;B = B.next;m--;}return null;}
}

142.環形鏈表II

第一遍-看題解后一遍過

• 思路：
  • 20mins的思考，想到了slowNode每次+1，fastNode每次+2；
  • 但這樣單純的移動，會導致兩個點相遇的時候不在入口，答案錯誤；
  • 最后還是看了題解，感覺不太能想得出來；

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode fastNode = head;ListNode slowNode = head;while (fastNode != null && fastNode.next != null) {slowNode = slowNode.next;fastNode = fastNode.next.next;if (fastNode == slowNode) {while (head != fastNode) {head = head.next;fastNode = fastNode.next;}return head;}}return null;}
}