企业官网建设流程全解析

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

力扣24. 两两交换链表中的节点

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

注意点

node0 node1 node2 node3

dummy 1 2 3 4 5

两两交换的话，先判断一下node0和node1的next是不是null，就是判断是否还有可以交换的节点。

有的话，就node0指向node2，node2指向node1，node1指向node3，这样子就变成了

node0 node2 node1 node3

dummy 2 1 3 4 5

然后需要开启下一轮遍历的话，更新node0为node1，更新node1为node3。

node2和node3会自动更新

​ node0 node1 node2 node3

dummy 2 1 3 4 5

最后遍历结束，返回头节点。

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0, head); ListNode node0 = dummy; ListNode node1 = head; while(node0.next != null && node1.next != null) { ListNode node2 = node1.next; ListNode node3 = node2.next; node0.next = node2; node2.next = node1; node1.next = node3; node0 = node1; node1 = node3; } return dummy.next; } }

时空复杂度分析

单层循环，需要遍历n/2次，因此时间复杂度为O(n)

空间复杂度为O(1)

力扣19. 删除链表的倒数第N个节点

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

注意点

双指针做法。

快指针先走n个节点，然后快慢指针再一起开始扫描，这样子当快指针到尾节点的时候时候，慢指针的下一个节点就是目标节点。

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode slow = dummy; ListNode fast = dummy; while (n -- > 0) { fast = fast.next; } while (fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next; } }

时空复杂度分析

加起来一共遍历了n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

力扣160. 相交链表

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

注意点

就是需要让两个链表走共同的路程，之后保证停留在相同节点（如果本来就无法相遇，那么就是都停留在空节点上）

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p = headA; ListNode q = headB; while (p != q) { p = p != null ? p.next : headB; q = q != null ? q.next : headA; } return p; } }

时空复杂度分析

单层循环，需要遍历m+n次，m+n为两个链表长度之和，因此时间复杂度为O(m+n)

空间复杂度为O(1)

力扣142. 环形链表 II

链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

注意点

设头节点到入环口需要走a步。设环长为c。设相遇的时候，慢指针走了b步，那么快指针走了2b步。

设快指针比慢指针多走了k圈，即2b－b=kc，得b=kc。

慢指针从入环口开始，在环中走了b－α=kc－α步到达相遇点。

这说明从相遇点开始，再走a步，就恰好走到入环口了！

虽然不知道a是多少，但如果让头节点和慢指针同时走，恰好a步后二者必定相遇，且相遇点就在入环口

代码

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (fast == slow) { while (slow != head) { slow = slow.next; head = head.next; } return head; } } return null; } }

时空复杂度分析

双层循环，但是外层循环只进行1次，内层循环也进行1次，且两层循环每次最多n的常数倍数，因此时间复杂度为O(n)

空间复杂度为O(1)

参考

https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html