【面试算法笔记】0203-链表-链表其他操作

个人主页https://github.com/zbhgis前言本系列主要记录自己学习算法的过程中的感悟。力扣24. 两两交换链表中的节点链接https://leetcode.cn/problems/swap-nodes-in-pairs/description/注意点node0 node1 node2 node3dummy 1 2 3 4 5两两交换的话先判断一下node0和node1的next是不是null就是判断是否还有可以交换的节点。有的话就node0指向node2node2指向node1node1指向node3这样子就变成了node0 node2 node1 node3dummy 2 1 3 4 5然后需要开启下一轮遍历的话更新node0为node1更新node1为node3。node2和node3会自动更新​ node0 node1 node2 node3dummy 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; } }时空复杂度分析单层循环需要遍历mn次mn为两个链表长度之和因此时间复杂度为O(mn)空间复杂度为O(1)力扣142. 环形链表 II链接https://leetcode.cn/problems/linked-list-cycle-ii/description/注意点设头节点到入环口需要走a步。设环长为c。设相遇的时候慢指针走了b步那么快指针走了2b步。设快指针比慢指针多走了k圈即2bbkc得bkc。慢指针从入环口开始在环中走了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