24. 两两交换链表中的节点
学习链接
个人思路
还是用虚拟节点，
- cur→cur.next.next
- cur.next.next→cur.next
- cur移动
解题代码
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { let dummy = new ListNode(null) dummy.next = head let cur = dummy while(cur.next && cur.next.next){ let two = cur.next.next let one = cur.next one.next = two.next cur.next = two two.next = one cur = one // 注意这里是跳到下一位，而不是cur.next } return dummy.next };
按图解释没啥问题
19.删除链表的倒数第N个节点
学习链接
个人想法
这道题只需要slow、fast双指针，中间间隔是n（拿到删除节点的上一个节点），然后到fast.next为空结束遍历，然后处理slow节点的删除即可+
解题代码
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { let dummy = new ListNode(0,head) let slow = dummy let fast = dummy for(let i = 0; i < n; i++){ fast = fast.next } while(fast.next){ slow = slow.next fast = fast.next } slow.next = slow.next.next return dummy.next };
160. 链表相交
学习链接
个人思路
如果相交，这两个链表必然结尾相连，计算两个链表长度差，直到两个长度相同，然后比较val相同，next相同，证明相交
解题代码
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ const getLength = (head)=>{ let length = 0 let cur = head while(cur){ cur = cur.next length ++ } return length } /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let lengthA = getLength(headA) let lengthB = getLength(headB) if(lengthA < lengthB){ // 如果A比B短，交换A、B [headA, headB] = [headB , headA]; [lengthA, lengthB] = [lengthB, lengthA]; } let diff = lengthA - lengthB while(diff){ headA = headA.next diff -- } while(headA && headB){ if(headA === headB){ return headA } headA = headA.next headB = headB.next } return null };
142.环形链表II
学习链接
个人想法
这道题一开始没什么思路，直接看文章学习，发现是一个数学问题，使用双指针，fast一次走两步，slow一次走一步，如果有环必然在环内相交（追击问题）
但是怎么着环的入口呢
我们发现 如果相遇，slow必然走了x+y，fast走x+y+n*(y+z) （多走n圈）
所以就是
2(x + y) = x + y + n(y + z) => x + y = n(y + z)因为我们要求x值，所以
x = N个环长度 - y 所以 如果在头结点设置一个指针index1，相遇节点设置一个index2 ，每次都走一步，两者必然在入口相交
因为
x = N个环长度 - y 走完x 必然是一圈少y，我们从相遇节点出发，刚好走到环形入口节点解题代码
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { if(!head || !head.next){ return null } let slow = head.next let fast = head.next.next while(fast && fast.next){ slow = slow.next fast = fast.next.next if(slow === fast){ // 找到相遇节点，开始计算 let temp = slow let cur = head while(temp !== cur){ // 一直找到两个节点相等返回值 temp = temp.next cur = cur.next } return temp } } return null };
很巧妙的数学问题，要多学习