《leetcode-go》插入法排序链表

使用插入法排序链表

注意：一定要保持链表的完整性，否则容易丢数据

package mainimport "fmt"type ListNode struct {Val  intNext *ListNode
}func main() {a1 := new(ListNode)a1.Val = 1a2 := new(ListNode)a2.Val = 2a3 := new(ListNode)a3.Val = 3a1.Next = a2a2.Next = a3ret := sortList(a1)for ret != nil {fmt.Println(ret.Val)ret = ret.Next//break}
}/**** @param head ListNode类* @return ListNode类*/
func sortList(head *ListNode) *ListNode {// write code hereif head == nil || head.Next == nil {return head}newHead := &ListNode{Val:  0,Next: head,}lastNode := headnode1 := head.Nextfor node1 != nil {node2 := newHeadtmp := node1.NextlastTmp := node1for node2.Next != node1 {//从大到小if node1.Val > node2.Next.Val {node1.Next = node2.Nextnode2.Next = node1lastNode.Next = tmplastTmp = lastNodebreak}//从小到大if node1.Val < node2.Next.Val {node1.Next = node2.Nextnode2.Next = node1lastNode.Next = tmplastTmp = lastNodebreak}node2 = node2.Next}node1 = tmplastNode = lastTmp}return newHead.Next
}