25.md

合并两个排序的链表

题目

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0≤n≤10000，−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,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}

思路

运用游标

实现

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// 合并两个排序的链表
func main() {
	var one *ListNode
	for _, v := range [3]int{5, 3, 1} {
		node := ListNode{
			Val:  v,
			Next: one,
		}
		one = &node
	}
	var two *ListNode
	for _, v := range [3]int{6, 4, 2} {
		node := ListNode{
			Val:  v,
			Next: two,
		}
		two = &node
	}
	Merge(one, two)
}

func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	result := ListNode{
		Val:  -1,
		Next: nil,
	}
	cur := &result
	for {
		if pHead1 == nil || pHead2 == nil {
			break
		}
		if pHead1.Val >= pHead2.Val {
			cur.Next = pHead2
			pHead2 = pHead2.Next
		} else {
			cur.Next = pHead1
			pHead1 = pHead1.Next
		}
		cur = cur.Next
	}
	if pHead1 != nil {
		cur.Next = pHead1
	} else if pHead2 != nil {
		cur.Next = pHead2
	}
	return result.Next
}