21. 合并两个有序链表

题目描述

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

示例

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

解法

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	var (
		l *ListNode
		p *ListNode
	)
	if l1 == nil && l2 == nil {
		return nil
	}
	l = &ListNode{}
	p = l
	for l1 != nil || l2 != nil {
		if l1 == nil {
			p.Val = l2.Val
			l2 = l2.Next
		} else if l2 == nil {
			p.Val = l1.Val
			l1 = l1.Next
		} else if l1.Val > l2.Val {
			p.Val = l2.Val
			l2 = l2.Next
		} else {
			p.Val = l1.Val
			l1 = l1.Next
		}
		if l1 == nil && l2 == nil {
			p.Next = nil
		} else {
			p.Next = &ListNode{}
			p = p.Next
		}
	}
	return l
}

本地测试

package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func createListNode(a []int) *ListNode {
	var head *ListNode
	if len(a) < 1 {
		return head
	}
	head = &ListNode{Val: a[0]}
	p := head
	a = a[1:]
	for _, item := range a {
		n := ListNode{Val: item}
		p.Next = &n
		p = p.Next
	}
	return head
}

func printListNode(head *ListNode) {
	for head.Next != nil {
		fmt.Print(head.Val, " -> ")
		head = head.Next
	}
	if head != nil {
		fmt.Print(head.Val, "\n")
	}
}

func main() {
	a, b := createListNode([]int{1, 2, 4}), createListNode([]int{1, 3, 4})
	printListNode(a)
	printListNode(b)
	printListNode(mergeTwoLists(a, b))
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists