🥈

Insertion Sort List

Created

2021/12/17 08:27

문제 번호

147

카테고리

Linked List

Sorting

Insertion Sort List - LeetCode

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head. The steps of the insertion sort algorithm: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.

https://leetcode.com/problems/insertion-sort-list/

Code

제출 날짜	시간	메모리
2021/12/17	12 ms	3.4 MB

// 147. Insertion Sort List
//
// https://leetcode.com/problems/insertion-sort-list/description/

// Definition for singly-linked list.
// type ListNode struct {
//     Val int
//     Next *ListNode
// }

// insertionSortList function sort the element of ListNode with ascending order.
// ListNode will be sorted by insertion sort as its function name.
// To find the place of the element, cursor moves from the start of the dummy to the end.
// Dummy holds the empty ListNode, so the answer is the Next of Dummy.
func insertionSortList(head *ListNode) *ListNode {
	dummy := new(ListNode)
	for head != nil {
		cur := dummy
		for cur.Next != nil && cur.Next.Val < head.Val {
			cur = cur.Next
		}
		cur.Next, head.Next, head = head, cur.Next, head.Next
	}
	return dummy.Next
}
Go
복사