How to sort the linked list in big data

I would like to share with you how to sort big data's linked list. I believe most people don't know much about it, so share this article for your reference. I hope you will gain a lot after reading this article. let's learn about it!

Algorithm:

For the sorting of linked lists, it is generally designed to split and merge two steps, split this step:

The middle node is used as the critical value, the small one on the left and the big one on the right.

Merge procedure:

Connect two ordered linked lists together.

Topic 1: separate linked lists

Https://leetcode-cn.com/problems/partition-list/submissions/

Code implementation:

/ * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode *} * / func partition (head * ListNode X int) * ListNode {if head = = nil {return nil} curr: = head before: = new (ListNode) before1: = before after: = new (ListNode) after1: = after for curr! = nil {if curr.Val < x {before.Next = curr before = before.Next} else {after.Next = curr after= After.Next} curr = curr.Next} before.Next = nil after.Next = nil if after1.Next! = nil {before.Next = after1.Next / / the location of the after first node before the after1 record offset} return before1.Next / / because the before1 first node is a none node. } / * solution: this can be split into two linked lists, those less than x are put into before, and those greater than or equal to are put into after. Then put the two linked lists together. , /

Execution result:

Topic 2:

Https://leetcode-cn.com/problems/partition-list-lcci/submissions/

Code implementation:

/ * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode *} * / func partition (head * ListNode, x int) * ListNode {L1, L2: = new (ListNode), new (ListNode) res,res1: = L1 L2 for head! = nil {if head.Val < x {l1.Next = & ListNode {Val:head.Val} L1 = l1.Next} else {l2.Next = & ListNode {Val:head.Val} L2 = l2.Next} head = head.Next} l1.Next = res1.Next return res.Next} / / double pointer sort Those less than x are put in L1, and those greater than x are put in L2. Finally, string the two linked lists together.

Execution result:

Topic 3: sort linked list

Https://leetcode-cn.com/problems/sort-list/

Code implementation:

/ * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode * * / func sortList (head * ListNode) * ListNode {/ / merge: 1. First split, dichotomy split, fast and slow pointer; 2. Merging Double pointer mode if head = = nil | | head.Next = = nil {return head} / / Fast and slow pointers find the corresponding intermediate position node sLING f: = head Head.Next / / do not point to the same node for f! = nil & & f.Next! = nil {s = s.Next f = f.Next.Next} tmp: = s.Next s.Next = nil / / Recursive operation left and right linked list l: = sortList (head) r: = sortList (tmp) pre: = new (ListNode) res: = pre / / merge the left and right linked lists for l! = nil & & r! = nil {if l.Val < r.Val {pre.Next = l = l.Next} else {pre.Next = r = r.Next} pre = pre.Next} if l! = nil {pre.Next = l } else if r! = nil {pre.Next = r} return res.Next}

Execution result:

The above is all the contents of the article "how to sort the linked list in big data". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!