链表
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。
在编写链表过程中，要注意边界测试，比如 index 为 0 size -0 size 时
删除链表中的节点
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
var deleteNode = function(node) {
var afterNode = node.next;
node.val=afterNode.val;
node.next=afterNode.next
};
反转一个单链表
递归
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;
}
迭代头插法
var reverseList = function(head){
let prev = null;
let curr = head;
while(curr !=null){
let netxTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
}
判断一个链表是否有环
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
var hasCycle = function(head) {
if(head==null)return false;
let fastNode = head.next;
let lowNode = head;
while(fastNode!=lowNode){
if (fastNode == null || fastNode.next == null) {
return false;
}
fastNode = fastNode.next.next;
lowNode = lowNode.next;
}
return true;
}
环形链表 II
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
var addTwoNumbers = function(l1, l2) {
let result = new ListNode(null);
let nextRst = result;
let isAdd=false;
while(l1!=null||l2!=null){
let sum = (l1?l1.val:0)+(l2?l2.val:0)+(isAdd?1:0);
if (sum>=10) {
isAdd=true;
}else{
isAdd=false;
}
nextRst.next = new ListNode(sum%10);
nextRst = nextRst.next
if(l1 != null) l1 = l1.next
if(l2 != null) l2 = l2.next
}
if(isAdd){
nextRst.next = new ListNode(1);
}
return result.next;
};
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var removeNthFromEnd = function(head, n) {
let count = 0;
let newHead = head;
let ary =[];
while(head!=null){
ary.push(head);
head=head.next;
}
if(n==1){
let node = ary[ary.length>1?ary.length-n-1:ary.length-n];
if(node.next){
node.next= null
}else{
newHead=null;
}
}else{
let deleteNode = ary[ary.length-n];
let nextNode = deleteNode.next;
deleteNode.next = nextNode?nextNode.next:null;
deleteNode.val = nextNode?nextNode.val:null;
}
return newHead;
};
合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var mergeTwoLists = function(l1, l2) {
let newHead = new ListNode(null);
let head = newHead;
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
head.next=l1;
l1=l1.next;
}else{
head.next=l2;
l2=l2.next;
}
head = head.next;
}
head.next=l1==null?l2:l1;
return newHead.next;
};
- 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var swapPairs = function(head) {
let dummy = new ListNode(-1);
dummy.next = head;
let prevNode = dummy;
while ((head != null) && (head.next != null)) {
// Nodes to be swapped
let firstNode = head;
let secondNode = head.next;
// Swapping
prevNode.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;
// Reinitializing the head and prevNode for next swap
prevNode = firstNode;
head = firstNode.next; // jump
}
return dummy.next;
};
