链表.md

链表

核心点

• null/nil 异常处理
• dummy node 哑巴节点
• 快慢指针
• 插入一个节点到排序链表
• 从一个链表中移除一个节点
• 翻转链表
• 合并两个链表
• 找到链表的中间节点

链表的数据结构

/**
 * Definition for singly-linked list.
 */
function ListNode(val) {
     this.val = val;
     this.next = null;
 }

练习

83.删除排序链表中的重复元素 remove-duplicates-from-sorted-list

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

var deleteDuplicates = function(head) {
    let current = head;
    while(current !== null && current.next !== null){
        if(current.val === current.next.val){
            current.next = current.next.next;
        }else{
            current = current.next;
        }
    }
    return head;
};

var deleteDuplicates = function(head) { // 递归写法
    if(head === null || head.next === null){
        return head;
    }
    head.next = deleteDuplicates(head.next);
    return head.val === head.next.val ? head.next : head;
};

82.删除排序链表中的重复元素Ⅱremove-duplicates-from-sorted-list-ii

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

var deleteDuplicates = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    let dummy = new ListNode(-1);
    dummy.next = head;
    let front = dummy;
    let back = head.next;
    while(back !== null){
        if(front.next.val !== back.val){
            front = front.next;
            back = back.next;
        } else {
            while(back !== null && front.next.val === back.val){
                back = back.next;
            }
            front.next = back;
            back = back === null ? null : back.next;
        }    
    }
    return dummy.next;
};

206.反转一个单链表（头插法）。reverse-linked-list

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

var reverseList = function(head) {
    if(head === null || head.next === null) return head;
    let dummy = new ListNode(-1);
    while(head !== null){
        let p = head.next;
        head.next = dummy.next;
        dummy.next = head;
        head = p;
    }
    return dummy.next;
};

92.反转链表Ⅱ reverse-linked-list-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 dummy = new ListNode(-1);
    dummy.next = head; //哑巴节点
    head = dummy;
    for(let i=m;i>1;i--){
        head = head.next; // 让head指向反转子列表的前一个节点
    }
    let pre = head.next; //指向子列表的第一个节点
    for(let j=m;j<n;j++){
        let post = pre.next; 
        pre.next = post.next; //头插法
        post.next = head.next;
        head.next = post;
    }
    return dummy.next;
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

// 迭代法
var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(-1);
    let pre = dummy;
    while(l1 !== null && l2 !== null){
        if(l1.val <= l2.val){
            pre.next = l1;
            l1 = l1.next;
        }else{
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;
    }
    pre.next = l1 === null ? l2 : l1;
    return dummy.next;
};

//递归
var mergeTwoLists = function(l1, l2) {
    if(l1 === null){
        return l2;
    }else if(l2 === null){
        return l1;
    }else if(l1.val <= l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
    }
};

86.分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5

var partition = function(head, x) {
    let biggerX = new ListNode(0);
    let post = biggerX;
    let smallerX = new ListNode(0);
    let pre = smallerX;
    let temp;
    while(head !== null){
        temp = head.next;
        if(head.val < x){
            pre.next = head;
            pre = pre.next;
        }else{
            post.next = head;
            post = post.next;
        }
        head = temp;
    }
    post.next = null; //最后一个的下一个指向为空，否则会出现环
    pre.next = biggerX.next;
    return smallerX.next;
};

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。O(nlogn)时间复杂度，常数级空间。

var sortList = function (head) {
    return mergeSort(head)
};

const findMidNode = head => {
    let slow = head
    let fast = head.next
    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

const mergeTwoList = (l1, l2) => {
    const dummy = new ListNode(0)
    let p = dummy
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            p.next = l1
            l1 = l1.next
        } else {
            p.next = l2
            l2 = l2.next
        }
        p = p.next
    }
    if (l1 !== null) { // l1不为空，p指向剩下的链表
        p.next = l1
    }
    if (l2 !== null) {
        p.next = l2
    }
    return dummy.next
}

const mergeSort = head => {
    if (head === null || head.next === null) {
        return head
    }
    let mid = findMidNode(head)
    let tail = mid.next
    mid.next = null
    let left = mergeSort(head)
    let right = mergeSort(tail)
    return mergeTwoList(left, right)
}

143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

var reorderList = function (head) {
    const nodeArr = []
    let node = head
    while (node !== null) {
        nodeArr.push(node)
        node = node.next
    }
    let i = 0, j = nodeArr.length - 1
    while (i < j) {
        nodeArr[i].next = nodeArr[j]
        i++
        if (i === j) break
        nodeArr[j].next = nodeArr[i]
        j--
    }
    nodeArr[i].next = null
}

141. 环形链表

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

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

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

var detectCycle = function (head) {
    let visited = new Set()  //使用哈希表，空间复杂度O(n)
    while (head !== null) {
        if(visited.has(head)){
            return head
        }
        visited.add(head)
        head = head.next
    }
    return null
};

var detectCycle = function (head) {  
    if (head === null || head.next === null) {
        return null
    }
    let slow = head
    let fast = head.next
    while(fast !== null && fast.next !== null){
        if(fast === slow) { //数学推导，看官网题解
            slow = slow.next
            fast = head
            while(fast !== slow){ 
                slow = slow.next
                fast = fast.next
            }
            return slow
        }
        slow = slow.next
        fast = fast.next.next
    }
    return null
};

234. 回文链表

请判断一个链表是否为回文链表。

var isPalindrome = function (head) {
    if (head === null || head.next === null) {
        return true
    }
    let slow = head
    let fast = head.next
    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }
    let tail = reverseList(slow.next)
    slow.next = null
    while (head !== null && tail !== null) {
        if (head.val !== tail.val) {
            return false
        }
        head = head.next
        tail = tail.next
    }
    return true
};

const reverseList = head => {
    if (head === null) {
        return head
    }
    const dummy = new ListNode(0)
    let prev = head
    while (prev !== null) {  //头插法
        let temp = prev
        prev = prev.next
        temp.next = dummy.next
        dummy.next = temp
    }
    return dummy.next
}

138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

var copyRandomList = function (head) {
    if (head === null) {
        return head
    }
    let cur = head
    while (cur !== null) {
        const clone = new Node(cur.val, cur.next, cur.random)
        const temp = cur.next
        cur.next = clone
        cur = temp
    }
    cur = head
    while (cur !== null) {
        if (cur.random !== null) {
            cur.next.random = cur.random.next
        }
        cur = cur.next.next
    }
    cur = head
    let cloneHead = cur.next
    while (cur !== null && cur.next !== null) {
        const temp = cur.next
        cur.next = cur.next.next
        cur = temp
    }
    return cloneHead
}; 

练习

• remove-duplicates-from-sorted-list
• remove-duplicates-from-sorted-list-ii
• reverse-linked-list
• reverse-linked-list-ii
• merge-two-sorted-lists
• partition-list
• sort-list
• reorder-list
• linked-list-cycle
• linked-list-cycle-ii
• palindrome-linked-list
• copy-list-with-random-pointer