Solution 1 - Iterative with Dummy Node
Use a dummy head and repeatedly append the smaller current node, then attach the remaining list.
Use a dummy head and repeatedly append the smaller current node, then attach the remaining list.
""" 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""List Node"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def mergeTwoLists(
self, a: Optional[ListNode], b: Optional[ListNode]
) -> Optional[ListNode]:
"""Merge Two Sorted Lists Function"""
dummy = cur = ListNode()
while a and b:
if a.val <= b.val:
cur.next = a
a = a.next
else:
cur.next = b
b = b.next
cur = cur.next
cur.next = a or b
return dummy.next
#####################################################################################
# Functions
#####################################################################################
def arr(head: Optional[ListNode]):
"""Collect list values"""
out = []
while head:
out.append(head.val)
head = head.next
return out
def testcase():
"""Test Function"""
a = ListNode(1, ListNode(3))
b = ListNode(2, ListNode(4))
print(arr(Solution().mergeTwoLists(a, b)))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()/** 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
/** Merge Two Sorted Lists Function */
mergeTwoLists(a, b) {
const dummy = new ListNode();
let cur = dummy;
while (a && b) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = a || b;
return dummy.next;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function arr(head) {
/** Collect list values */
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function testcase() {
/** Test Function */
const a = new ListNode(1, new ListNode(3));
const b = new ListNode(2, new ListNode(4));
console.log(arr(new Solution().mergeTwoLists(a, b)));
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();/** 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
constructor(public val: number = 0, public next: ListNode | null = null) {}
}
class Solution {
/** Merge Two Sorted Lists Function */
mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
const dummy = new ListNode();
let cur: ListNode = dummy;
while (a && b) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = a || b;
return dummy.next;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function arr(head: ListNode | null): number[] {
/** Collect list values */
const out: number[] = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function testcase(): void {
/** Test Function */
const a = new ListNode(1, new ListNode(3));
const b = new ListNode(2, new ListNode(4));
console.log(arr(new Solution().mergeTwoLists(a, b)));
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();// 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node
package main
/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type ListNode struct {
Val int
Next *ListNode
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func mergeTwoLists(a *ListNode, b *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for a != nil && b != nil {
if a.Val <= b.Val {
cur.Next = a
a = a.Next
} else {
cur.Next = b
b = b.Next
}
cur = cur.Next
}
if a != nil {
cur.Next = a
} else {
cur.Next = b
}
return dummy.Next
}
func arr(head *ListNode) []int {
out := []int{}
for head != nil {
out = append(out, head.Val)
head = head.Next
}
return out
}
func testcase() {
// Test Function
a := &ListNode{Val: 1, Next: &ListNode{Val: 3}}
b := &ListNode{Val: 2, Next: &ListNode{Val: 4}}
fmt.Println(arr(mergeTwoLists(a, b)))
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
testcase()
}// 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct ListNode {
val: i32,
next: Option<Box<ListNode>>,
}
/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl ListNode {
fn new(val: i32) -> Self {
ListNode { val, next: None }
}
}
struct Solution;
impl Solution {
/// Merge Two Sorted Lists Function
pub fn merge_two_lists(
a: Option<Box<ListNode>>,
b: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
match (a, b) {
(None, x) | (x, None) => x,
(Some(mut x), Some(mut y)) => {
if x.val <= y.val {
x.next = Solution::merge_two_lists(x.next.take(), Some(y));
Some(x)
} else {
y.next = Solution::merge_two_lists(Some(x), y.next.take());
Some(y)
}
}
}
}
}
fn main() {
let a = Some(Box::new(ListNode::new(1)));
let b = Some(Box::new(ListNode::new(2)));
println!("{:?}", Solution::merge_two_lists(a, b));
}