打卡第4天----链表
通过学习基础，发现我的基本功还得需要再练练，思路得再更加清晰明了，这样子做算法题才能驾轻就熟。每天记录自己的进步。
一、两两交换
题目编号：24
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
依然采用虚拟头节点，本题还需要定一个临时temp变量，用来临时保存节点。
图解思路：
JS 代码如下，完全是按照卡尔的视频讲解来的，放在leetcode上可以提交通过：
var swapPairs = function(head) {
const dummyHead = new ListNode();
//虚拟头节点指向链表的真实头节点
dummyHead.next = head;
//定一个一个临时指针，用来遍历链表
let curr = dummyHead;
//循环的终止条件，二者的顺序一点也不能交换
while (curr.next && curr.next.next) {
//临时指针，趁节点的指向还没变，先保存一下，免得要用的时候没有
const temp = curr.next;
const temp1 = curr.next.next.next;
//开始进行节点交换
curr.next = curr.next.next;
curr.next.next = temp;
temp.next = temp1;
//向后移动
curr = curr.next.next;
}
return dummyHead.next;
};
二、删除节点
题目编号：19
题目描述：
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
思路图解：
具体的JS代码如下，在力扣上可以通过提交的：
// 用双指针去解决这道题
var removeNthFromEnd = function(head, n) {
// 创建虚拟头节点
const dummyHead = new ListNode()
// 让虚拟头节点指向头节点
dummyHead.next = head;
let fast = dummyHead;
let slow = dummyHead;
// 先让fast指针移动n + 1步
while (n >= 0) {
fast = fast.next;
n--;
}
// 遍历链表，当fast指针为null的时候，slow指针正好停留在倒数第n个节点的前一个节点
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 通过slow执行删除操作
slow.next = slow.next.next;
// 返回删除后的节点
return dummyHead.next;
};三、链表相交
题目编号：面试题 02.07. 链表相交
题目描述：
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。
思路图解：
JS代码如下，是可以在leetcode上提交通过的：
// 封装一个方法用来获取链表的长度
function getLinkLength(head) {
let len = 0, curr = head;
while (curr) {
len++;
curr = curr.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let currA = headA, currB = headB,
lenA = getLinkLength(headA),
lenB = getLinkLength(headB);
// 让A链表始终为长的那个链表
if (lenA < lenB) {
[currA, currB] = [currB, currA];
[lenA, lenB] = [lenB, lenA];
}
let i = lenA - lenB;
// 让currA向前移动i步，保持移动之后的链表A和链表B是长度相同的
while (i-- > 0) {
currA = currA.next;
}
// 此时开始对两个链表遍历，若两链表不相等，指针向后移动，继续比较
while (currA && currA != currB) {
currA = currA.next;
currB = currB.next;
};
// 若两链表相等，则直接返回
return currA;
};四、环形链表
题目编号：142:环形链表
题目描述：
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。
原文地址：https://blog.csdn.net/qq_35770417/article/details/140229049
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！