第一遍-递归-小看了一下题解
- 思路：
- 读了两遍题目才理解…
- 相邻节点的交换，这个操作很容易实现，但需要一个
tmpNode - 因为是链表的题目，没开始思考之前先加了
dummyNode，还真管用 - 把
dummyNode作为了最后返回用的，以及新增preNode作为tmpNode - 用递归写是因为不想用循环了…感觉递归写起来好玩一些
- 小看了一下题解的地方：（其实再给自己多一些debug的次数应该也能试出来）
- 递归结束条件：
|| i.next.next == null这个没有想出来
package LinkList;public class Linklist_test {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();
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) {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;}
}
第一遍
- 思路：
- 这一题误操作了，忘记先自己想了，直接看题解了…
- 算是两遍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;}slow.next = slow.next.next;return dummy.next;}
}
第一遍
- 思路：
- 读了第一遍直接写了，第一次开始写循环又出错了…而且出了两个错误
- 错误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;}
}
第一遍-看题解后一遍过
- 思路：
- 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;}
}
