【面试算法笔记】0203-链表-链表其他操作
个人主页：https://github.com/zbhgis
前言
本系列主要记录自己学习算法的过程中的感悟。
力扣24. 两两交换链表中的节点
链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
注意点
1.
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
2.
然后需要开启下一轮遍历的话，更新node0为node1，更新node1为node3。
node2和node3会自动更新
node0 node1 node2 node3
dummy 2 1 3 4 5
3.
最后遍历结束，返回头节点。
代码
/**
* 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