代码随想录Day4
今日任务
24.两两交换链表中的节点
19.删除链表的倒数第N个节点
面试题02.07.链表相交
142.环形链表Ⅱ
语言：Java
24. 两两交换链表中的节点
考点：链表
链接：https://leetcode.cn/problems/swap-nodes-in-pairs/
解题思路：事先在草稿纸上模拟一遍，考虑清楚几种情况（链表为空/链表只有一个元素，直接返回头结点即可；链表元素个数为奇数；链表元素个数为偶数）
/**
* 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) {
if(head == null || head.next == null){
return head;
}
ListNode dimmyHead = new ListNode(0, head);
ListNode preNode = dimmyHead;
ListNode firstNode = head;
ListNode secondNode = firstNode.next;
while(firstNode != null && firstNode.next != null){
firstNode.next = secondNode.next;
secondNode.next = firstNode;
preNode.next = secondNode;
preNode = firstNode;
if(firstNode != null && firstNode.next != null){
firstNode = firstNode.next;
secondNode = firstNode.next;
}
}
return dimmyHead.next;
}
}
19. 删除链表的倒数第N个节点
考点：链表
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
注意事项：我们要删除某个元素时，应该保证curNode停留在要删除元素的前一个才方便进行操作，所以在写循环终止条件时，会有减1的问题。
缺点：没有通过一个循环实现
改进：快慢指针，一个循环实现，需要注意的是先让快指针移动 n+1 个位置，方便慢指针后续的删除操作。
/**
* 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) {
if(head == null){
return head;
}
ListNode dummyHead = new ListNode(0, head);
ListNode curNode = head;
int len = 1;
while(curNode != null){
len++;
curNode = curNode.next;
}
curNode = dummyHead;
int moveTime = len - n;
//循环的终止条件务必减1，否则curNode会直接到我们要删除元素的位置
for(int i = 0; i < moveTime - 1; i++){
curNode = curNode.next;
}
if(curNode.next != null){
curNode.next = curNode.next.next;
}
return dummyHead.next;
}
}
改进版
/**
* 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 dummyHead = new ListNode(0, head);
ListNode slow = dummyHead;
ListNode fast = dummyHead;
for(int i = 0; i < n; i++){
fast = fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
if(slow.next != null){
slow.next = slow.next.next;
}
return dummyHead.next;
}
}
面试题02.07. 链表相交
考点：链表
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
注意事项：第一次写的时候直接比较的是curNodeA和curNodeB的值是否相等，如果相等返回curNodeA / curNodeB，但是很显然这样得到的结果就不符合示例1的情况，所以改为直接比较两个节点是否相等。
这一点在英文版的题目说明中更清晰一些
/**
* 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) {
if(headA == null || headB == null){
return null;
}
int lenA = 1;
int lenB = 1;
ListNode curNodeA = headA;
ListNode curNodeB = headB;
while(curNodeA.next != null){
curNodeA = curNodeA.next;
lenA++;
}
while(curNodeB.next != null){
curNodeB = curNodeB.next;
lenB++;
}
if(curNodeA != curNodeB){
return null;
}
if(lenA > lenB){
curNodeA = headA;
curNodeB = headB;
int moveTime = lenA - lenB;
for(int i = 0; i < moveTime; i++){
curNodeA = curNodeA.next;
}
while(curNodeA != null){
//是指针相等不是值相等
if(curNodeA == curNodeB){
return curNodeA;
}
else{
curNodeA = curNodeA.next;
curNodeB = curNodeB.next;
}
}
}
else{
curNodeA = headA;
curNodeB = headB;
int moveTime = lenB - lenA;
for(int i = 0; i < moveTime; i++){
curNodeB = curNodeB.next;
}
while(curNodeB != null){
if(curNodeB == curNodeA){
return curNodeB;
}
else{
curNodeA = curNodeA.next;
curNodeB = curNodeB.next;
}
}
}
return null;
}
}
时间复杂度：O(m+n)
空间复杂度：O(1)
看Python解法时突然get一个新方法，不用事先计算长度，逻辑和删除环形链表有一点像
/**
* 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) {
if(headA == null || headB == null){
return null;
}
ListNode curA = headA;
ListNode curB = headB;
while(curA != curB){
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
}
142. 环形链表Ⅱ
考点：链表
链接：https://leetcode.cn/problems/linked-list-cycle-ii/
自己没有写出来，看了卡哥的视频
需要明确的一些问题：
- 为何 fast 步长为2，slow 步长为1？
为了保证 fast 和 slow 之间不错过去，fast 要以1的速度追 slow。 - 为何能保证 fast 和 slow 一定在环里相遇？
如果一个链表中有环，fast 一定会先进入环，一旦 fast 进入环，那么 fast 就会一直在环中移动，也会在环中和 slow 相遇。 - 为何 slow 一定会在进入环的第一圈内被 fast 追上？
具体可以看卡哥的文章，图片画的很清晰。 - 为何 fast 和 slow 相遇前在环中走的圈数没有考虑的必要？
不论 fast 在和 slow 相遇前走了多少圈，我们需要明确的是一旦确认了相遇位置 index1，我们就可以通过相遇位置 index1 和头结点位置 index2 确定环入口位置，不管 fast 在此之前走了多少圈，我们都可以让 index1 和 index2 在环入口处相遇，从而得到环入口位置。 - 如何确定环的入口？（见上问）
/**
* 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(slow == fast){
ListNode index1 = slow; //fast也可
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1; //index2也可
}
}
return null;
}
}
