javascript 链表部分算法题

导航

• 反转链表
• 两个链表第一个公共节点
• 找出有环链表环入口节点
• 链表内指定区间反转
• 合并K个已排序的链表

反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

比如：1->2->3->4，反转后： 4->3->2->1

function ListNode(x){
    this.val = x;
    this.next = null;
}
// 翻转链表
function ReverseList(pHead) {
    // 方法1 （最优）空间复杂度 O(1)，时间复杂度 O(n)，常数项1。
    //console.time('timeing')
    let cur = pHead, pre = null, nex = null
    while(cur != null) {
        nex = cur.next
        cur.next = pre
        pre = cur
        cur = nex
    }
    //console.timeEnd('timeing')
    return pre;

    // 方法2 （更慢）空间复杂度 O(n)，时间复杂度 O(n),常数项2。
    // let cur = pHead
    // let arr = []
    // while(cur) {
    //     arr.push(cur.val)
    //     cur = cur.next
    // }
    // arr.reverse()  // 反转值顺序
    // cur = pHead
    // let i = 0
    // while(cur) {
    //     cur.val = arr[i++]
    //     cur = cur.next
    // }
    // return pHead;
}
//自建数据 1~1000,0000 节点
let pHead = new ListNode(1);
let temp = pHead;
for (let i =1; i < 10000000; i++){
    let one =  new ListNode(i + 1);
    temp.next = one;
    temp = temp.next;
}
ReverseList(pHead)

module.exports = {
    ReverseList : ReverseList
};

两个链表第一个公共节点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n \le 1000n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

function ListNode(x){
    this.val = x;
    this.next = null;
}

function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let cur1 = pHead1, cur2 = pHead2, len1 =0, len2 = 0;
    // 获取长度
    while(cur1 || cur2) {
        if (cur1) {
             len1++;
             cur1 = cur1.next
        }
        if (cur2) {
            len2++;
            cur2 = cur2.next
        }
    }
    // 开始走
    cur1 = pHead1
    cur2 = pHead2
    // 长的先走几步
    let step = Math.abs(len1 - len2)
    if (len1 > len2) {
        while(step) {
            cur1 = cur1.next
            step--
        }
    }else {
        while(step) {
            cur2 = cur2.next
            step--
        }
    }
    // 一起走时，进行值判断
    while (cur1) {
        if(cur1.val === cur2.val) {
            return cur1
        }
        cur1 = cur1.next
        cur2 = cur2.next
    }
    return null
}

// 测试数据 两个链表， 第4个节点重合
let pHead1 = new ListNode(1);
let temp = pHead1;
for (let i =1; i < 3; i++){
    let one =  new ListNode(i + 1);
    temp.next = one;
    temp = temp.next;
}
let pHead2 = new ListNode(4);
let temp2 = pHead2;
for (let i =4; i < 6; i++){
    let one =  new ListNode(i + 1);
    temp2.next = one;
    temp2 = temp2.next;
}
for (let i = 6; i < 10; i++){
    let one =  new ListNode(i + 1);
    temp.next = one;
    temp2.next = one;
    temp = temp.next;
    temp2 = temp2.next;
}
let c = FindFirstCommonNode(pHead1, pHead2)
let tt = c
while (tt) {
    console.log('t-', tt.val)
    tt = tt.next
}
// 链1：1 2 3  7 8 9 10
// 链2：4 5 6  7 8 9 10
// 打印 7 8 9 10
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};

找出有环链表环入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

function ListNode(x){
    this.val = x;
    this.next = null;
}

function EntryNodeOfLoop(pHead) {
    // 方法一 Map方式  时间复杂度：O(n)，空间复杂度：O(n) 
    // let cur = pHead, map = new Map()
    // while(cur) {
    //     if(!map.has(cur.val)) {
    //         map.set(cur.val, cur)
    //     }else {
    //         return map.get(cur.val)
    //     }
    //     cur = cur.next
    // }
    // return null
    
    // 方法二 快慢指针  时间复杂度：O(n)，空间复杂度：O(1) 
    let fast = pHead, slow = pHead
    while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(!fast || !fast.next) break
        if ( fast.val === slow.val) break  // 相遇节点c
    }
    // 如果是因为while条件而终止，则表示没有环
    if (fast == null || fast.next == null) return null   
    // slow 此时是相遇节点C， fast从头出发，直到相遇则为入口节点b
    fast = pHead   
    while(fast.val !== slow.val) {
        fast = fast.next
        slow = slow.next
    }
    return fast
}

// 有环单链表返回环入口节点
let pHead1 = new ListNode(1);
let temp = pHead1;
let add = null
for (let i =1; i < 9; i++){
    let one =  new ListNode(i + 1);
    if( i === 5) {
        add = one
    }
    temp.next = one;
    temp = temp.next;
}
temp.next = add;
let c = EntryNodeOfLoop(pHead1)
console.log('环入口：',c.val)
let tt = pHead1, j = 0;
while (j < 20) {
    console.log('t-', tt.val)
    tt = tt.next
    j++
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

快慢指针证明：如图

链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→null, m=2,n=4,
返回 1→4→3→2→5→null

进阶：时间复杂度 O(n)，空间复杂度 O(1)

思路

先将m ~ n的后半段逆向，在m和n同时递进（同时交换值），再将m ~ n的后半段方向转回来，返回头结点。

function ListNode(x){
    this.val = x;
    this.next = null;
}
function reverseBetween( head ,  m ,  n ) {
    // 时间复杂度 O(n)，空间复杂度 O(1)
    if (m === n) return head
    let cur = head, nex = null, pre = null
    let i = 1, mid = m + ((n-m)>>1)
    let L = null, R = null
    // mid ~ n 指向反转
    while (cur) {
        if(i == m) L = cur   // m 节点
        if (i >= mid + 1) {
            if(i <= n) {
                if(i == n) R = cur  // n 节点
                nex = cur.next
                cur.next = pre
                pre = cur
                cur = nex
            }else {
                break
            }
        }else {
            pre = cur
            cur = cur.next
        }
        i++
    }
    // 交换值
    i = m, left = L, right = R
    while (i <= mid) {
        [left.val, right.val] = [right.val, left.val] 
        left = left.next
        right = right.next
        i++
    }
    // mid ~ n 指向再转回来
    i = n, pre = cur, cur = R   // pre = n的下一节点
    while(i>= mid) {
        nex = cur.next
        cur.next = pre
        pre = cur
        cur = nex
        i--
    }
    return head
}

// 测试
let pHead1 = new ListNode(1);
let temp = pHead1;
for (let i =1; i < 10; i++){
    let one =  new ListNode(i + 1);
    temp.next = one;
    temp = temp.next;
}
temp.next = null;
console.log('pHead1--', pHead1)

let newHead = reverseBetween(pHead1, 1,10)

let tt = newHead, j = 0;
while (tt && j < 20) {
    console.log('t-', tt.val)
    tt = tt.next
    j++
}
module.exports = {
    reverseBetween : reverseBetween
};

合并K个已排序的链表

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数满足 0 <= n <= 10^5，链表个数满足 1 <= k <= 10^5 ，每个链表的长度满足 1 <= len <= 200 ，每个节点的值满足 |val| <= 1000∣val∣<=1000

要求：时间复杂度 O(nlogk)

思路 使用归并，将数组划分成左右两个，然后合并成一个，递归向下，最后返回结果。

function ListNode(x){
    this.val = x;
    this.next = null;
}

function partition(leftH, rightH) {
    if (!leftH) return rightH
    if (!rightH) return leftH

    let bool = leftH.val <= rightH.val // 左边那个是否小于右边那个
    let head = bool? leftH : rightH
    let temp = head
    let L = bool? leftH.next : leftH, 
        R = bool? rightH : rightH.next
        
    while(L && R) {
        let k = null
        if(L.val <= R.val) {
            k = L
            L = L.next
            
        }else {
            k = R
            R = R.next
        }
        temp.next = k
        temp = temp.next
    }
    if (L) {  // L 还有尾巴
        temp.next = L
    }
    if (R) {  //或者  R 还有尾巴
        temp.next = R
    }
    return head
}
// 时间复杂度 O(nlogk)
function merge(lists, m, n) {
    if(m === n)  return lists[m]
    let mid = m + ((n-m)>>1)
    let leftH = merge(lists, m, mid)
    let rightH = merge(lists, mid+1, n)
    return partition(leftH, rightH)
}


/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */
function mergeKLists( lists ) {
    // write code here
    if (!lists.length) return null
    return merge(lists, 0, lists.length -1)
    
}
// 测试
let LIST = [];
let pHead1 = new ListNode(1);
let temp = pHead1;
for (let i =1; i < 2; i++){
    let one =  new ListNode(i +1);
    temp.next = one;
    temp = temp.next;
}
temp.next = null;

let pHead2 = new ListNode(1);
let temp2 = pHead2;
for (let i =3; i < 5; i++){
    let one =  new ListNode(i +1);
    temp2.next = one;
    temp2 = temp2.next;
}
temp2.next = null;
LIST.push(pHead1);   // 1 2
LIST.push(pHead2);  // 1 4 5

// console.log('LIST--', LIST)

let newHead = mergeKLists(LIST)
let tt = newHead, j = 0;
while (tt && j < 50) {
    console.log('t-', tt.val)
    tt = tt.next
    j++
}
module.exports = {
    mergeKLists : mergeKLists
};