精美大气的餐饮类企业网站,电力建设规范下载网站,网站开发提成,广告投放代理商加盟24. 两两交换链表中的节点
第一遍-递归-小看了一下题解
思路#xff1a; 读了两遍题目才理解…相邻节点的交换#xff0c;这个操作很容易实现#xff0c;但需要一个tmpNode因为是链表的题目#xff0c;没开始思考之前先加了dummyNode#xff0c;还真管用把dummyNode作为…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每次1fastNode每次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;}
}
