合并两个有序列表

题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

Go语言版本解决方案：

package merge_two_sorted_lists

// ListNode 是链接节点
type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果有一条链为nil,直接返回另一条链
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    //在l1和l2之间，选择较小的节点作为head,并设置好node
    var head, node *ListNode
    if l1.Val < l2.Val {
        head = l1
        node = l1
        l1 = l1.Next
    } else {
        head = l2
        node = l2
        l2 = l2.Next
    }

    //循环比较l1和l2的值，始终选择较小的值连上node
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            node.Next = l1
            l1 = l1.Next
        } else {
            node.Next = l2
            l2 = l2.Next
        }

        //至此，head才是一个完整的链
        node = node.Next
    }

    //剩余节点的处理
    if l1 != nil {
        node.Next = l1
    }

    if l2 != nil {
        node.Next = l2
    }

    return head
}


package merge_two_sorted_lists

import (
    "fmt"
    "github.com/stretchr/testify/assert"
    "testing"
)

type question struct {
    para
    ans
}

//para 是参数
//one 代表第一个参数
type para struct {
    one []int
    two []int
}

// ans 代表答案
// one 代表第一个答案
type ans struct {
    one []int
}

func TestMergeTwoSortedLists(t *testing.T) {
    ast := assert.New(t)
    qs := []question{
        question{
            para{[]int{}, []int{1, 3, 5, 7}},
            ans{[]int{1, 3, 5, 7}},
        },
        question{
            para{[]int{1, 3, 5, 7}, []int{}},
            ans{[]int{1, 3, 5, 7}},
        },
        question{
            para{[]int{1, 3, 5, 7}, []int{2, 4, 6, 8}},
            ans{[]int{1, 2, 3, 4, 5, 6, 7, 8}},
        },
        question{
            para{[]int{10, 20, 30}, []int{1, 2, 3}},
            ans{[]int{1, 2, 3, 10, 20, 30}},
        },
        question{
            para{[]int{1, 3, 5},
                []int{2, 4, 6, 8, 10},
            },
            ans{[]int{1, 2, 3, 4, 5, 6, 8, 10}},
        },
        question{
            para{[]int{1, 3, 5, 7, 9},
                []int{2, 4, 6},
            },
            ans{[]int{1, 2, 3, 4, 5, 6, 7, 9}},
        },
    }

    for _, q := range qs {
        a, p := q.ans, q.para
        fmt.Printf("~~%v~~\n", p)

        ast.Equal(a.one, l2s(mergeTwoLists(s2l(p.one), s2l(p.two))), "输入:%v", p)
    }

}

// convert *ListNode to []int
func l2s(head *ListNode) []int {
    var res []int

    for head != nil {
        res = append(res, head.Val)
        head = head.Next
    }
    return res
}

//convert []int to *ListNode

func s2l(nums []int) *ListNode {
    if len(nums) == 0 {
        return nil
    }

    res := &ListNode{
        Val: nums[0],
    }

    temp := res
    for i := 1; i < len(nums); i++ {
        temp.Next = &ListNode{Val: nums[i]}
        temp = temp.Next
    }

    return res
}