链表
链表判环(快慢指针)
[141.环形判环]: https://leetcode.cn/problems/linked-list-cycle/
解题思想：
- 先判断head节点是否为空
- 再利用快慢指针来判断，如果两个指针能够相等，则有环，否则快指针首选到尾节点后判断为null，则无环
(在javascript中，return null的结果为true，在c++中，return NULL的结果为false)
var hasCycle = function(head) { if(head === null) return false; let p1 = head; let p2 = head.next; while(p2 && p2.next) { if(p1 === p2) return true; p1 = p1.next; p2 = p2.next.next; } return false; };
[142.环形链表]: https://leetcode.cn/problems/linked-list-cycle-ii/
解题思想：
- 如果链表的头节点或者第二个节点为null，则非循环链表
- 然后进行快慢指针的相遇，如果快指针的q.next为null或者q.next.next为null则非循环链表
- 如果快慢指针能够相遇，则说明是循环链表
- 要找到循环的首节点，让慢指针重新从头节点开始走，让快指针恢复成慢指针的速度
- 当他们相遇的时候就是循环链表的首节点
var detectCycle = function(head) { if(head === null || head.next === null) return null; let p = head, q = head; do { if(q.next === null || q.next.next === null) return null; p = p.next q = q.next.next } while(p != q) p = head; while(p !== q) { p = p.next; q = q.next; } return p; };
[202.快乐数]: https://leetcode.cn/problems/happy-number/
解题思想：
- 一个数组的每个位置平方和确定，可想象成链表形式，这个节点指向下一个节点
- 先写出对应求平方和的方法，对一个数取余并平方，然后依此求下一位的平方
- 然后将1看作链表中的null值即可按照链表判断有无环的方式进行判断是否为快乐数
function getNext(x) { let z = 0; while(x) { z += (x % 10) * (x % 10); x = parseInt(x / 10); } return z; } var isHappy = function(n) { if(n === 1) return true; let p = n, q = n; do { if(getNext(q) === 1 || getNext(getNext(q)) === 1) return true; p = getNext(p); q = getNext(getNext(q)); } while(p !== q); return false; };
链表反转
[206.反转链表]: https://leetcode.cn/problems/reverse-linked-list/
解题思路：
- 利用三个节点进行迭代反转
- 如果链表为null,则直接返回即可
- 利用三个节点反转，pre表示反转头，cur表示未反转头，下个带反转头
var reverseList = function(head) { if(head === null) return head; let pre = null, cur = head, p = head.next; while(cur) { cur.next = pre; pre = cur; (cur = p) && (p = p.next); } return pre; };
2. 利用递归反转
- 递归从尾节点进行反转
- 当当前head为null或者head->next为null时表示为尾节点，返回head
- 然后递归将head->next节点指向head节点
- 然后将head节点指向null
var reverseList = function(head) { if(head==null || head.next==null) return head let p = reverseList(head.next) head.next.next = head head.next = null return p };
[返回倒数第K个节点]: https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
解题思路：
- 利用前后指针
- 先让前指针先走k-1步
- 然后两个指针再一同走，如果前指针走到尾节点，后指针就在倒数第k个节点
var kthToLast = function(head, k) { let p1 = head; let p2 = head; while(--k) { p1 = p1.next; } while(1) { if(p1.next === null) { return p2.val; } p1 = p1.next; p2 = p2.next; } };
链表删除节点
[19.删除链表的倒数第N个结点]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
解题思路：
- 先创建一个虚拟头节点
- 利用前后指针找到需要删除的节点的前一个节点
- 将要删除的前一个节点指向被删除节点的后一个节点
- 然后返回虚拟头节点的下一个节点
var removeNthFromEnd = function(head, n) { let p = new ListNode(-1), res = p;p1 = p, p2 = p; p.next = head; while(n--) { p1 = p1.next; }; while(1) { if(p1.next === null) { p2.next = p2.next.next; return res.next; } p1 = p1.next; p2 = p2.next; }; };
[82.删除排序链表中重复元素]: https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/submissions/
解题思路：
- 创建虚拟头节点
- 循环判断当前结点的下一个结点和下下个结点不为空，进入循环判断
- 如果当前结点的下一个结点值等于下下个结点值，将这个值临时存储
- 当下一个结点存在，并且这个结点等于临时存储的值时，将当前结点指向下下个结点，即删除重复元素
- 最后返回虚拟头节点的下一个结点
var deleteDuplicates = function(head) { if(head === null) return head; let p = new ListNode(0, head), cur = p; while(cur.next && cur.next.next) { if(cur.next.val === cur.next.next.val) { let temp = cur.next.val; while(cur.next && cur.next.val === temp) { cur.next = cur.next.next; } } else { cur = cur.next; } } return p.next; };
[83.删除排序链表中的重复元素]: https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
解题思路：
- 声明头节点，并判断当前结点的下一个结点是否存在
- 再判断当前结点值是否等于下一结点值，如果相等，就将当前结点指向下下个结点，即删除重复结点
- 最后返回头结点
var deleteDuplicates = function(head) { let p = head; if(head === null) return null; while(p.next) { if(p.val === p.next.val) { p.next = p.next.next; } else { p = p.next; } } return head; };
虚拟头节点：链表头地址可能发生改变
