[Go] Linked list - Merge Two Sorted Lists

 

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

My code

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	merge := &ListNode{}
	head := merge

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

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

	return head.Next
}

https://go.dev/play/p/LWaEztxvxjj

• I made merge variable as empty ListNode
• head will remember start address of merge.
• in for loop, they will run until list1, 2 are empty.
• after that, if condition will check whether list1 or list2 is nil.
• So they will point rest of them.
• head.Next has start of merge.
• when he allocate address from merge, address will be changed.

 

sample 0 ms submission

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummyHead := ListNode{}
    p := &dummyHead

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            p.Next = list1
            list1 = list1.Next
        } else {
            p.Next = list2
            list2 = list2.Next
        }
        p = p.Next
    }
    
    if list1 != nil { p.Next = list1 }
    if list2 != nil { p.Next = list2 }
    return dummyHead.Next
}

sample 1 ms submission & sample 2600 KB submission

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {return list2}
    if list2 == nil {return list1}
    
    if list1.Val <= list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }   
}

• This code is recursion, but i need to understand for using or modifying codes from others.

sample 2 ms submission

func addToResult(list **ListNode, newList **ListNode) {
    (*newList).Next = *list
    *list = (*list).Next
    *newList = (*newList).Next
    (*newList).Next = nil
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    var result *ListNode
    
    if list1 == nil {
        return list2
    }
    
    if list2 == nil {
        return list1
    }
    
    if list1.Val <= list2.Val {
        result = list1
        list1 = list1.Next
    } else {
        result = list2
        list2 = list2.Next
    }
    
    newList := result

LOOP:
    for list1 != nil || list2 != nil {
        if list2 == nil {
            newList.Next = list1
            break LOOP
        }
        
        if list1 == nil {
            newList.Next = list2
            break LOOP
        }
        
        if list1.Val <= list2.Val {
            newList.Next = list1
            newList = list1
            list1 = list1.Next
        } else {
            newList.Next = list2
            newList = list2
            list2 = list2.Next
        } 
        
    }
    
    return result
}

sample 3 ms submission

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dump := &ListNode{}
    temp := dump
    for list1 != nil && list2 != nil {
        if list1.Val > list2.Val{
            temp.Next = list2
            list2 = list2.Next
        }else {
            temp.Next = list1
            list1 = list1.Next
        }
        temp = temp.Next
    }
    if list1 != nil {
        temp.Next = list1
    }
    if list2 != nil {
        temp.Next = list2
    }
    return dump.Next
}

sample 4 ms submission & sample 2500 KB submission

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    root := &ListNode{}
    curr := root
    for list1 != nil || list2 != nil {
        curr.Next = &ListNode{}
        curr = curr.Next
        if list1 != nil && list2 != nil {
            if list1.Val < list2.Val {
                curr.Val = list1.Val
                list1 = list1.Next
            } else {
                curr.Val = list2.Val
                list2 = list2.Next
            }
        } else if list1 != nil {
            curr.Val = list1.Val
            list1 = list1.Next
        } else {
            curr.Val = list2.Val
            list2 = list2.Next
        }
    }
    return root.Next
}

sample 2400 KB submission

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    currentNode := dummyHead
    
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            currentNode.Next = list1
            list1 = list1.Next
        } else {
            currentNode.Next = list2
            list2 = list2.Next
        }
        currentNode = currentNode.Next
    }
    if list1 != nil {
        currentNode.Next = list1
    }
    
    if list2 != nil {
        currentNode.Next = list2
    }
    return dummyHead.Next
}