Merge Two Sorted Linked Lists in Go

Program Code

package main

import "fmt"

// ListNode defines a node in a singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// mergeTwoLists merges two sorted linked lists and returns it as a new sorted list
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    // Traverse both lists and merge them
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val { current.Next = l1 l1 = l1.Next } else { current.Next = l2 l2 = l2.Next } current = current.Next } // Append the remaining nodes of the non-empty list if l1 != nil { current.Next = l1 } else { current.Next = l2 } return dummy.Next } // Helper function to print the linked list func printList(head *ListNode) { for head != nil { fmt.Print(head.Val, " ") head = head.Next } fmt.Println() } // Main function to test the mergeTwoLists function func main() { // Create first sorted linked list: 1 -> 2 -> 4
    l1 := &ListNode{1, &ListNode{2, &ListNode{4, nil}}}

    // Create second sorted linked list: 1 -> 3 -> 4
    l2 := &ListNode{1, &ListNode{3, &ListNode{4, nil}}}

    // Merge the two lists
    mergedList := mergeTwoLists(l1, l2)

    // Print the merged list
    fmt.Print("Merged List: ")
    printList(mergedList)
}
    

Explanation

The Go program is designed to merge two sorted linked lists into a single sorted linked list. Below is a breakdown of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list. Each node contains a value (Val) and a pointer to the next node (Next).

2. mergeTwoLists Function

The mergeTwoLists function takes two pointers to the heads of two sorted linked lists as input and returns a pointer to the head of a new sorted linked list. The function uses a dummy node to simplify the merging process:

• dummy serves as the starting point of the merged list.
• current keeps track of the last node in the merged list.
• It iterates through both lists, comparing the nodes and appending the smaller node to the merged list.
• After the loop, it appends any remaining nodes from the non-empty list.

3. printList Function

The printList function is a helper function used to print the elements of a linked list.

4. Main Function

The main function creates two example sorted linked lists, merges them using mergeTwoLists, and prints the merged list.