merge_sort_linked_list

merge_sort_linked_list.go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    var dummy = new(ListNode)
    var p = dummy
    
	rabbit := list1
	turtle := list2
    
    for rabbit != nil && turtle != nil {
        if  rabbit.Val < turtle.Val {
            p.Next = rabbit
            rabbit = rabbit.Next
        } else {
            p.Next = turtle
            turtle = turtle.Next
        }
        p = p.Next
    }

    if rabbit != nil {
        p.Next = rabbit
    } else {
        p.Next = turtle
    }

	return dummy.Next

}