公司做网站建设价格,网站设计与运营第二次,音乐网页制作素材,固安建设行政主管部门官方网站24. 两两交换链表中的节点
题目链接#xff1a;https://leetcode.cn/problems/swap-nodes-in-pairs/
注意点#xff1a;
遍历链表的时候什么时候截止#xff08;避免空指针异常或无限死循环的问题#xff09;#xff1f; 节点数量为偶数或链表为空时#xff0c;cur.ne…24. 两两交换链表中的节点
题目链接https://leetcode.cn/problems/swap-nodes-in-pairs/
注意点
遍历链表的时候什么时候截止避免空指针异常或无限死循环的问题 节点数量为偶数或链表为空时cur.next null 为 true 时即可终止循环 节点数量为奇数时cur.next.next null 为true 时即可终止循环 while(cur.next ! null cur.next.next ! null){}交换的代码具体怎么写
解题思路
定义一个虚拟头节点dummyhead操作的指针curcur dummyhead一定要指向要反转的两个节点的前一个节点如图所示 根据反转后的结果来看cur指向22指向11指向3 具体操作如下 最后返回链表
代码
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyhead new ListNode(-1); // 定义一个虚拟头节点dummyhead.next head;ListNode cur dummyhead;ListNode temp1;ListNode temp2;while(cur.next ! null cur.next.next ! null){temp1 cur.next; // 临时节点保存两个节点之中的第一个节点temp2 cur.next.next.next; // 临时节点保存下一轮交换中的两个节点中的第一个节点cur.next cur.next.next; cur.next.next temp1;temp1.next temp2;cur cur.next.next;}return dummyhead.next;}
}19.删除链表的倒数第N个节点
题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
注意点
操作指针要指向被删除节点的前一个节点
如何找到倒数的第n个节点设置快慢指针。
解题思路
定义一个虚拟头节点省去对头节点的特殊判断设置一个快指针一个慢指针让快指针先移动n1步然后快慢指针再同时移动直到快指针指向空节点这样慢指针就指向了被删除的节点的前一个节点。
代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyhead new ListNode(-1);dummyhead.next head;ListNode slow dummyhead; // 慢指针ListNode fast dummyhead; // 快指针// 快指针向前移动n1位for(int i0;in;i){fast fast.next;}// 同时移动快慢指针while(fast ! null){fast fast.next;slow slow.next;}// 删除节点slow.next slow.next.next;return dummyhead.next;}
}142.环形链表II
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/
注意点
判断链表是否有环设置快慢指针有环的情况下快慢指针一定会相遇。
如何找到环的入口
解题思路
定义快慢指针快指针从起点出发以每次走两个节点的速度前进慢指针从起点出发以每次走一个节点的速度前进如果两个指针相遇说明这个链表有环。
再定义两个节点一个从头结点出发一个从快慢指针相遇的节点出发当这两个指针相遇时此节点便是环的入口节点。
代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head; // 快指针ListNode slow head; // 慢指针while(fast ! null fast.next ! null){fast fast.next.next; // 快指针走两步slow slow.next; // 慢指针走一步if(fast slow){ // 找到了环ListNode index1 fast; // 从快慢指针的相遇点出发ListNode index2 head; // 从头出发while(index1 ! index2){ // 相遇处就是环的入口处index1 index1.next;index2 index2.next;}return index1;}}return null;}
}
