打卡第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。