21. Merge sorted lists

21_solution1.c

#include "list_node.h"

struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2) {
  struct ListNode dummy;
  struct ListNode *tail = &dummy;

  while (list1 != NULL && list2 != NULL) {
    if (list1->val <= list2->val) {
      tail->next = list1;
      list1 = list1->next;
    } else {
      tail->next = list2;
      list2 = list2->next;
    }
    tail = tail->next;
  }

  tail->next = (list1 != NULL) ? list1 : list2;

  return dummy.next;
}

21_solution2.c

#include "list_node.h"

struct ListNode *mergeTwoLists(struct ListNode *a, struct ListNode *b) {
  if (!a)
    return b;
  if (!b)
    return a;
  if (a->val <= b->val) {
    a->next = mergeTwoLists(a->next, b);
    return a;
  }
  b->next = mergeTwoLists(a, b->next);
  return b;
}

list_node.h

#pragma once

#include <stddef.h>

// Definition for singly-linked list.
struct ListNode {
  int val;
  struct ListNode *next;
};

21_solution1_iterative.cpp

#include "list_node.h"

class Solution {
public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    ListNode dummy; // stack-allocated dummy head
    ListNode *tail = &dummy;

    while (list1 != nullptr && list2 != nullptr) {
      if (list1->val <= list2->val) {
        tail->next = list1;
        list1 = list1->next;
      } else {
        tail->next = list2;
        list2 = list2->next;
      }
      tail = tail->next;
    }

    // attach whichever list still has nodes left
    tail->next = (list1 != nullptr) ? list1 : list2;

    return dummy.next;
  }
};

21_solution2_recursive.cpp

#include "list_node.h"

class Solution {
public:
  ListNode *mergeTwoLists(ListNode *a, ListNode *b) {
    if (!a)
      return b;
    if (!b)
      return a;
    if (a->val <= b->val) {
      a->next = mergeTwoLists(a->next, b);
      return a;
    }
    b->next = mergeTwoLists(a, b->next);
    return b;
  }
};

list_node.h

#pragma once

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

21_solution1.go

package linkedlists

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

21_solution2.go

package linkedlists

func mergeTwoLists(a *ListNode, b *ListNode) *ListNode {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }
    if a.Val <= b.Val {
        a.Next = mergeTwoLists(a.Next, b)
        return a
    }
    b.Next = mergeTwoLists(a, b.Next)
    return b
}

list_node.go

package linkedlists

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

21_solution1.java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        tail.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
}

21_solution2.java

class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null)
            return b;
        if (b == null)
            return a;
        if (a.val <= b.val) {
            a.next = mergeTwoLists(a.next, b);
            return a;
        }
        b.next = mergeTwoLists(a, b.next);
        return b;
    }
}

ListNode.java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

21_solution1.js

const ListNode = require("./list_node");

var mergeTwoLists = function (list1, list2) {
  const dummy = new ListNode();
  let tail = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  tail.next = list1 !== null ? list1 : list2;

  return dummy.next;
};

21_solution2.js

const ListNode = require("./list_node");

var mergeTwoLists = function (a, b) {
  if (a === null) return b;
  if (b === null) return a;

  if (a.val <= b.val) {
    a.next = mergeTwoLists(a.next, b);
    return a;
  }
  b.next = mergeTwoLists(a, b.next);
  return b;
};

list_node.js

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

module.exports = ListNode;

21_solution1.py

from list_node import ListNode


class Solution:
    def mergeTwoLists(
        self, list1: ListNode, list2: ListNode
    ) -> ListNode:
        dummy = ListNode()
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 if list1 else list2

        return dummy.next

21_solution2.py

from list_node import ListNode


class Solution:
    def mergeTwoLists(self, a: ListNode, b: ListNode) -> ListNode:
        if not a:
            return b
        if not b:
            return a
        if a.val <= b.val:
            a.next = self.mergeTwoLists(a.next, b)
            return a
        b.next = self.mergeTwoLists(a, b.next)
        return b

list_node.py

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

21_solution1.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn merge_two_lists(
        mut list1: Option<Box<ListNode>>,
        mut list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        loop {
            match (list1, list2) {
                (Some(mut n1), Some(n2)) if n1.val <= n2.val => {
                    list1 = n1.next.take();
                    list2 = Some(n2);
                    tail.next = Some(n1);
                }
                (Some(n1), Some(mut n2)) => {
                    list2 = n2.next.take();
                    list1 = Some(n1);
                    tail.next = Some(n2);
                }
                (Some(n1), None) => {
                    tail.next = Some(n1);
                    break;
                }
                (None, Some(n2)) => {
                    tail.next = Some(n2);
                    break;
                }
                (None, None) => break,
            }
            tail = tail.next.as_mut().unwrap();
        }

        dummy.next
    }
}

21_solution2.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn merge_two_lists(
        a: Option<Box<ListNode>>,
        b: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (a, b) {
            (None, b) => b,
            (a, None) => a,
            (Some(mut a), Some(b)) if a.val <= b.val => {
                a.next = Self::merge_two_lists(a.next.take(), Some(b));
                Some(a)
            }
            (Some(a), Some(mut b)) => {
                b.next = Self::merge_two_lists(Some(a), b.next.take());
                Some(b)
            }
        }
    }
}

list_node.rs

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}