链表的合并算法实现

我们已经了解了链表的定义和基本的操作，如增删查改，现在，我们来看下如何连接两个链表成为新的链表，类似于Array.concat()和array_merge()方法。

链表的合并(JS版)

为了让问题变得典型，我们这里假设链表是单向有序的。

// 一个结点类
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// 一个链表
class List {
    constructor() {
        this.head = new Node('head');
    }
    // 展示链表中所有的值
    display() {
        let cur = this.head;
        while (cur.next !== null) {
            console.log(cur.next.data);
            cur = cur.next;
        }
    }
    // 查找结点在链表中的位置
    find(value) {
        let cur = this.head;
        while (cur.data !== value) {
            if (cur.next === null) {
                return null;
            }
            cur = cur.next;
        }
        return cur;
    }
    // 查找结点在链表中的前一个结点
    findPrev(value) {
        let cur = this.head;
        while (cur.next !== null) {
            if (cur.next.data === value) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    // 在指定结点后插入一个结点, 如果第2个参数为空，则插入在尾部
    insert(newValue, value) {
        let node = new Node(newValue);
        let cur = null;
        if (value === undefined) {
            cur = this.head;
            while (cur.next !== null) {
                cur = cur.next;
            }
        } else {
            cur = this.find(value);
            if (cur === null) {
                return false;
            }
        }
        node.next = cur.next;
        cur.next = node;
    }
    // 删除一个结点
    remove(value) {
        let prev = this.findPrev(value);
        if (prev !== null) {
            if (prev.next.next === null) {
                prev.next = null;
            } else {
                prev.next = prev.next.next;
            }
        }
    }
}

// 合并两个单向升序链表，并返回一个新的单向升序链表
function combineNodeList(l1, l2) {
    let list = new List();
    l0 = list.head;
    l1 = l1.head.next;
    l2 = l2.head.next;
    // 依次取两个链表的首部的较小值，直到其中一个走到尾部
    while (l1 !== null && l2 !== null) {
        if (l1.data < l2.data) {
            l0.next = new Node(l1.data);
            l1 = l1.next;
        } else {
            l0.next = new Node(l2.data);
            l2 = l2.next;
        }
        l0 = l0.next;
    }
    // 依次复制还未到尾部的链表结点，直到尾部
    let longList = l1 === null ? l2 : l1;
    while (longList !== null) {
        l0.next = new Node(longList.data);
        longList = longList.next;
    }
    return list;
}
复制代码

链表的合并（PHP版）

<?php 
// 定义结点
class Node {
    public $data = null;
    public $next = null;
    public function __construct($value) {
        $this->data = $value;
    }
}
// 定义单向升序列表（省略部分方法）
class LinkList {
    public $head = null;
    public function __construct() {
        $this->head = new Node('head');
    }
    public function display() {
        $cur = $this->head->next;
        while ($cur !== null) {
            echo $cur->data . '<br/>';
            $cur = $cur->next;
        }
    }
    public function find($value) {
        $cur = $this->head->next;
        while ($cur !== null) {
            if ($cur->data = $value) {
                return $cur;
            }
            $cur = $cur->next;
        }
        return false;
    }
    public function insert($value, $beforeValue = null) {
        if ($beforeValue === null) {
            $cur = $this->head;
            while ($cur->next !== null) {
                $cur = $cur->next;
            }
            $target = $cur;
        } else {
            $target = $this->find($beforeValue);
            if ($target === false) {
                return false;
            }
        }
        $node = new Node($value);
        $node->next = $target->next;
        $target->next = $node;
        return $node;
    }
    // 连接两个链表，返回新链表
    public static function combineList($list1, $list2) {
        $newList = new LinkList();
        $list = $newList->head;
        $l1 = $list1->head->next;
        $l2 = $list2->head->next;
        while ($l1 !== null && $l2 !== null) {
            if ($l1->data > $l2->data) {
                $list->next = new Node($l2->data);
                $l2 = $l2->next;
            } else {
                $list->next = new Node($l1->data);
                $l1 = $l1->next;
            }
            $list = $list->next;
        }
        $longList = $l1 === null ? $l2 : $l1;
        while ($longList !== null) {
            $list->next = new Node($longList->data);
            $longList = $longList->next;
            $list = $list->next;
        }
        return $newList;
    }
}

$l1 = new LinkList();
$l2 = new LinkList();
foreach([1,2,3,4,5] as $item) {
    $l1->insert($item);
};
$l1->display(); // 1,2,3,4,5
foreach([2,4,6,8,10] as $item) {
    $l2->insert($item);
};
$l2->display(); // 2,4,6,8,10
$l3 = LinkList::combineList($l1, $l2);
$l3->display(); // 1,2,2,3,4,4,5,6,8,10
?>
复制代码

参考资料

1. 【LeetCode021】合并有序链表：zhuanlan.zhihu.com/p/39274660
2. 链表的含义和代码实现（单向、双向、循环）：juejin.im/post/5c90fb…