【代码随想录算法训练营-第四天】【链表】24，19， 面试题 02.07，142

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;}
}