# 合并两个有序链表
---

:::success

package main

import "fmt"

//创建结点 结构体
type ListNode struct {
	Value int
	Next  *ListNode
}

// 创建链表结点
func NewListNode(v int) *ListNode {
	return &ListNode{v, nil}
}

// 递归合并
func mergeLinkList(l1, l2 *ListNode) *ListNode {
	// 两个有序链表都为空
	if l1 == nil && l2 == nil {
		return nil
	}

	// 其中一个链表为空，直接返回另一个链表
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	var (
		result *ListNode
	)

	// 链表都不空的时候
	if l1.Value >= l2.Value { // 当l1结点的值大于l2结点的值，那么result指向l2的结点，从l2开始遍历
		result = l2
		result.Next = mergeLinkList(l1, l2.Next)
	} else { // 当l2结点的值大于l1结点的值，那么result指向l1的结点，从l1开始遍历
		result = l1
		result.Next = mergeLinkList(l1.Next, l2)
	}

	return result
}

// 借助新的链表
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	var (
		tmp, result *ListNode
	)
	tmp = NewListNode(-1)
	result = tmp

	for l1 != nil && l2 != nil {
		if l1.Val >= l2.Val { // 当l1结点的值大于l2结点的值，那么result指向l2的结点，从l2开始遍历
			tmp.Next = l2
			l2 = l2.Next
		} else { // 当l2结点的值大于l1结点的值，那么result指向l1的结点，从l1开始遍历
			tmp.Next = l1
			l1 = l1.Next
		}
		tmp = tmp.Next
	}

	if l1 == nil {
		tmp.Next = l2
	}

	if l2 == nil {
		tmp.Next = l1
	}

	return result.Next // return result,会把初始化的头结点-1打印出来
}

func main() {
	l1 := NewListNode(1)
	l1.Append(2)
	l1.Append(3)
	l1.Append(3)
	l1.Append(7)
	l1.Show()

	l2 := NewListNode(5)
	l2.Append(6)
	l2.Append(6)
	l2.Append(8)
	l2.Append(9)
	l2.Append(10)
	l2.Show()

	p2 := mergeLinkList(l1, l2)
	p2.Show()
}

func (h *ListNode) Append(i int) {
	for h.Next != nil {
		h = h.Next
	}
	h.Next = &ListNode{Value:i}
}

func (h *ListNode) Show() {
	for h != nil {
		if h.Next != nil {
			fmt.Printf("%d->", h.Value)
		} else {
			fmt.Printf("%d\n", h.Value)
		}
		h = h.Next
	}
}

:::

1->2->3->3->7
5->6->6->8->9->10
1->2->3->3->5->6->6->7->8->9->10

###### tags: `LeeCode`