链表

一、链表:是一种基础数据结构，是一种线性表，不会按线性的顺序存储数据。

每一个结点存储一个数据和一个指向下一结点的地址（也叫后继指针next） 增、删的时间复杂度为O（1），查的时间复杂度为O（n）

1、常见链表

单链表：头结点记录链表基地址，尾结点的指针指向空地址null

循环链表：头结点记录链表基地址，尾结点的指针指向头结点

双向链表：每一个结点存储一个数据和一个指向下一结点的地址（也叫后继指针next），还有一个指向上一结点的地址（也叫前驱指针prev）

2、线性表（Linear List）。

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

二、leetcode题目

1、剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL

var reverseList = function(head) {
    let prev=null
    let curr=head
    while(curr){
        [curr.next,prev,curr]=[prev,curr,curr.next]
    }
    return prev
};

2、92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。

示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL

var reverseBetween = function(head, m, n) {
    let prev=null
    let curr=head
    for(let i=1;i<m;i++){
        prev=curr
        curr=curr.next
    }
    let prev2=prev
    let curr2=curr
    for(let i=m;i<=n;i++){
        [curr.next,prev,curr]=[prev,curr,curr.next]
    }
    if(prev2!==null){
        prev2.next=prev
    }else{
        head=prev
    }
    curr2.next=curr
    return head
};

3、141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

var hasCycle = function(head) {
    if(head==null){
        return false
    }
    let slow=head
    let fast=head
    while(fast.next!=null&&fast.next.next!=null){
        slow=slow.next
        fast=fast.next.next
        if(slow==fast){
            return true
        }
        
    }
    return false
};

4、剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

var mergeTwoLists = function(l1, l2) {
    let head=new ListNode(0)
    let curr=head
    while(l1&&l2){
        if(l1.val<=l2.val){
            curr.next=l1
            l1=l1.next
        }else{
            curr.next=l2
            l2=l2.next
        }
    curr=curr.next
    }

    curr.next=l1?l1:l2
    return head.next
};

5、