打卡第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)!