[数据结构与算法]leetcode 排序链表

递归merge会加大栈空间和时间
pre，cursor每次加大merge单元后都要从头开始
l2 找第二段unit的时候要注意nil判断

func sortList(head *ListNode) *ListNode {
	dataLen := 0
	for p := head; p != nil; p = p.Next {
		dataLen++
	}
	unitLen := 1
	dummyHead := ListNode{0, head}
	//cursor := head
	for unitLen < dataLen {
		cursor:=dummyHead.Next
		pre := &dummyHead  //每次要从头

		for cursor != nil {
			l1 := cursor
			for i := 1; i < unitLen && cursor.Next != nil; i++ {
				cursor = cursor.Next
			}
			l2 := cursor.Next
			cursor.Next = nil

			cursor = l2
			for i := 1; i < unitLen && cursor!=nil&&cursor.Next != nil; i++ {
				cursor = cursor.Next
			}
			var next *ListNode
			if cursor!=nil{
				next = cursor.Next
				cursor.Next = nil
			}
			cursor = next
			pre.Next = merge(l1, l2)
			for pre.Next != nil {
				pre = pre.Next
			}
			pre.Next = next
		}
		unitLen *= 2

	}
	return dummyHead.Next
}

func mergeTwo(list1, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		list1.Next = mergeTwo(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwo(list1, list2.Next)
		return list2
	}
}
func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    if temp1 != nil {
        temp.Next = temp1
    } else if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}