Merge Two Sorted Lists

                                            
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (list1 && 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 ? list1 : list2;
        
        return dummy.next;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

                                            
# Definition for singly-linked list.
# class  ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(0)
        current = dummy
        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        if list1:
            current.next = list1
        if list2:
            current.next = list2
        return dummy.next

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    while (list1 && list2) {
        struct ListNode** pp = list1->val < list2->val ? &list1 : &list2;
        tail->next = *pp;
        *pp = (*pp)->next;
        tail = tail->next;
    }
    
    tail->next = list1 ? list1 : list2;
    return dummy.next;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        
        if (list1.val < list2.val)
        {
            list1.next = MergeTwoLists(list1.next, list2);
            return list1;
        }
        else
        {
            list2.next = MergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    if (!l1) return l2;
    if (!l2) return l1;
    
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        $dummy = new 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;
        }
        
        if ($list1 != null) {
            $tail->next = $list1;
        }
        
        if ($list2 != null) {
            $tail->next = $list2;
        }
        
        return $dummy->next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        if list1 == nil {
            return list2
        } else if list2 == nil {
            return list1
        } else if list1!.val < list2!.val {
            list1!.next = mergeTwoLists(list1!.next, list2)
            return list1
        } else {
            list2!.next = mergeTwoLists(list1, list2!.next)
            return list2
        }
    }
}

                                            
class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        if (list1 == null) {
            return list2
        }
        if (list2 == null) {
            return list1
        }
        
        if (list1.`val` < list2.`val`) {
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            return list2
        }
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
      if (list1 == null) return list2;
      if (list2 == null) return list1;
      
      if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
      } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
      }
  }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

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

    if list1 != nil {
        current.Next = list1
    }

    if list2 != nil {
        current.Next = list2
    }

    return dummy.Next
}

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
    dummy = ListNode.new
    current = dummy
    
    while list1 && list2
        if list1.val < list2.val
            current.next = list1
            list1 = list1.next
        else
            current.next = list2
            list2 = list2.next
        end
        current = current.next
    end
    
    current.next = list1 if list1
    current.next = list2 if list2
    
    return dummy.next
end

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode = {
        if (list1 == null) return list2
        if (list2 == null) return list1

        if (list1.x < list2.x) {
            list1.next = mergeTwoLists(list1.next, list2)
            list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            list2
        }
    }
}

                                            
%% Definition for singly-linked list.
%%
%% -record(list_node, {val = 0 :: integer(),
%%                     next = null :: 'null' | #list_node{}}).
-spec merge_two_lists(List1 :: #list_node{} | null, List2 :: #list_node{} | null) -> #list_node{} | null.
merge_two_lists(null, List2) ->
    List2;
merge_two_lists(List1, null) ->
    List1;
merge_two_lists(#list_node{val = Val1, next = Next1} = List1, #list_node{val = Val2, next = Next2} = List2) when Val1 =< Val2 ->
    List1#list_node{next = merge_two_lists(Next1, List2)};
merge_two_lists(List1, List2) ->
    merge_two_lists(List2, List1).

                                            
# Definition for singly-linked list.

defmodule ListNode do
  @type t :: %__MODULE__{
          val: integer,
          next: ListNode.t() | nil
        }
  defstruct val: 0, next: nil
end

defmodule Solution do
  @spec merge_two_lists(list1 :: ListNode.t | nil, list2 :: ListNode.t | nil) :: ListNode.t | nil
  def merge_two_lists(nil, list) do
    list
  end

  def merge_two_lists(list, nil) do
    list
  end

  def merge_two_lists(list1 = %ListNode{val: val1, next: next1}, list2 = %ListNode{val: val2, next: next2}) when val1 <= val2 do
    new_next = merge_two_lists(next1, list2)
    %ListNode{val: val1, next: new_next}
  end

  def merge_two_lists(list1, list2) do
    merge_two_lists(list2, list1)
  end
end

To solve this coding challenge, we need to merge two sorted linked lists into a single sorted linked list. We will use a dummy node approach to simplify the process. Below is a detailed explanation of the methodology and pseudocode to solve this.

Explanation

The task requires merging two sorted linked lists into one sorted list, where the given linked lists are already sorted in non-decreasing order. The main idea is to iterate through both lists, comparing their current elements, and appending the smaller element to the result list. First, a dummy node is used as a starting point for the merged list. This makes it easier to handle edge cases, like when one or both input lists are empty. A pointer starts at the dummy node and is used to build our new sorted list. We then enter a loop where we compare the values at the heads of both lists. The smaller value is appended to the merged list, and we move the pointer in the list from which the element was taken. This process continues until we have processed all elements from both lists. Finally, if any elements remain in either list (because one list could be longer than the other), they are appended to the merged list since the remaining elements are already sorted.

Pseudocode with comments

                                            
// Define a class for the linked list nodes
class ListNode:
    function __init__(self, value=0, next=None):
        this.value = value       // Value of the node
        this.next = next         // Pointer to the next node

// Define the function to merge two sorted linked lists
function mergeTwoLists(list1, list2):
    // Create a dummy node to serve as the starting point of the merged list
    dummyNode = ListNode(0)
    
    // Create a pointer for the dummy node
    current = dummyNode

    // Loop until one of the lists runs out of elements
    while list1 is not null and list2 is not null:
        // Compare the values at the heads of both lists
        if list1.value < list2.value:
            current.next = list1  // Append list1's node to the merged list
            list1 = list1.next    // Move to the next node in list1
        else:
            current.next = list2  // Append list2's node to the merged list
            list2 = list2.next    // Move to the next node in list2
        
        // Move the current pointer to the next node
        current = current.next
    
    // If elements remain in list1, append them to the merged list
    if list1 is not null:
        current.next = list1
    
    // If elements remain in list2, append them to the merged list
    if list2 is not null:
        current.next = list2
    
    // Return the head of the merged list, which is the next node of our dummy node
    return dummyNode.next

Step-by-Step Explanation/Detailed Steps in Pseudocode

Define ListNode Class:

Construct the
ListNode

class with attributes for value and the next node pointer.

Create a Dummy Node:

Initialize a dummy node. This serves as the placeholder for the beginning of the merged list, making it easier to return the list at the end.

Initialize a Pointer:

Initialize
current

as a pointer to the dummy node. It will traverse and build the merged list.

Traverse and Compare Nodes:

Use a loop to go through both lists until one of them is exhausted.
Within the loop, compare the current values of
list1

and
list2

.
Append the smaller node to the merged list using
current.next

.
Move the pointer in the list from which the node was appended.
Move
current

to
current.next

.

Handle Remaining Nodes:

After exiting the loop, check if any nodes remain in
list1

. If yes, append them since they are already sorted.
Similarly, check if any nodes remain in
list2

and append them.

Return Merged List:

Return the merged list starting from
dummyNode.next

, skipping the dummy node itself since it was just a placeholder.

By following this structured approach, we can efficiently merge two sorted linked lists into one sorted list.