Merge Two Sorted Lists

Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

将两个有序链表合二为一

Solution

逐次比较l1、l2,将较小的那个结点添加到新链表尾部,并指向下一个结点

 1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
 9    if l1 == nil {
10        return l2
11    } else if l2 == nil {
12        return l1
13    }
14
15    var head, tail *ListNode
16
17    // 将首次判断放在循环外,可以减少判断次数,提高效率
18    if l1.Val < l2.Val {
19        head = l1
20        l1 = l1.Next
21    } else {
22        head = l2
23        l2 = l2.Next
24    }
25
26    tail = head
27
28    for {
29        if l1 == nil {
30            tail.Next = l2
31            break
32        } else if l2 == nil {
33            tail.Next = l1
34            break
35        } else if l1.Val < l2.Val {
36            tail.Next = l1
37            tail = l1
38            l1 = l1.Next
39        } else {
40            tail.Next = l2
41            tail = l2
42            l2 = l2.Next
43        }
44    }
45
46    return head
47}