合并两个排序的链表

发表于

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的

数据范围： 0≤n≤1000 ， -1000≤节点值≤1000

要求：空间复杂度O(1)，时间复杂度O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}

示例1

1
2
输入:  {1,3,5},{2,4,6}
返回:  {1,2,3,4,5,6}

示例2

1
2
输入:  {},{}
返回:  {}

示例3

1
2
输入:  {-1,2,4},{1,3,4}
返回:  {-1,1,2,3,4,4}

题解

迭代

设置 head 为虚拟节点，放置于新链表之前，最后返回的就是 head.next ；设置 cur 为当前节点，从 head 开始
当两个链表都非空时进入循环，令新链表的下一个节点 cur.next 为val更小的节点，相应的链表节点后移一位，每次循环记得 cur 也要后移一位。如果循环结束后还有链表非空， cur 指向非空链表，返回 head.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    head := &ListNode{}

    cur := head
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val < pHead2.Val {
            cur.Next = pHead1
            pHead1 = pHead1.Next
        } else {
            cur.Next = pHead2
            pHead2 = pHead2.Next
        }
        cur = cur.Next
    }

    if pHead1 != nil {
        cur.Next = pHead1
    }
    if pHead2 != nil {
        cur.Next = pHead2
    }

    return head.Next
}