Sort linked list python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Sort a linked list in O(n log n) time using constant space complexity.

License

stefanosbou/python-sort-linked-list

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Python sort single Linked list

Sort a linked list in O(n log n) time using constant space complexity.

• Use merge sort (in place — merging linked lists).
• Use runner technique to find the middle of the linked list. The runner technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The «fast» node will be hopping two nodes for each one node that the «slow» node iterates through.
• Then split the linked list at half and recursively call merge() on both linked lists. Merge using a basic merge() function on the two linked lists.

example usage:

>>> from sort_linked_list import Node, sort_list >>> node1 = Node(37) >>> node2 = Node(99) >>> node3 = Node(12) >>> node1.next = node2 >>> node2.next = node3 >>> >>> node = sort_list(node1) >>> node.traverse() 12 37 99

About

Sort a linked list in O(n log n) time using constant space complexity.

Источник

Sort for Linked Lists python

values := make a double ended queue by taking elements of values,insert value of node at the end of values,while node is not null, doinsert value of node at the end of valuesnode := next of node,value of node := left element of queue and delete element from left of queue

import collections class ListNode: def __init__(self, data, next = None): self.val = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_list(head): ptr = head print('[', end = "") while ptr: print(ptr.val, end = ", ") ptr = ptr.next print(']') class Solution: def solve(self, node): values = [] head = node while node: values.append(node.val) node = node.next values.sort() values = collections.deque(values) node = head while node: node.val = values.popleft() node = node.next return head ob = Solution() head = make_list([5, 8, 4, 1, 5, 6, 3]) print_list(ob.solve(head))

Input

Output

Answer by Morgan Ray

Sort a linked list that is sorted alternating ascending and descending orders?,Given a Linked List. The Linked List is in alternating ascending and descending orders. Sort the list efficiently. ,Alternate Odd and Even Nodes in a Singly Linked List,Delete alternate nodes of a Linked List

Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL Output List: 10 -> 12 -> 30 -> 40 -> 53 -> 67 -> 89 -> NULL Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL Output List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Given Linked List is 10 40 53 30 67 12 89 Sorted Linked List is 10 12 30 40 53 67 89

Answer by Josie Franco

Create a sorted singly linked list of numbers based upon user input. Program logic: Ask for a number, add that number to the list in sorted position, print the list. Repeat until they enter -1 for the number.,Asking for help, clarification, or responding to other answers.,4 years later, but I think that is easier in this way, Jobs Programming & related technical career opportunities

class Node: def __init__(self): self.data = None self.next = None class LinkedList: def __init__(self): self.head = None def addNode(self, data): curr = self.head if curr is None: n = Node() n.data = data self.head = n return if curr.data > data: n = Node() n.data = data n.next = curr self.head = n return while curr.next is not None: if curr.next.data > data: break curr = curr.next n = Node() n.data = data n.next = curr.next curr.next = n return def __str__(self): data = [] curr = self.head while curr is not None: data.append(curr.data) curr = curr.next return "[%s]" %(', '.join(str(i) for i in data)) def __repr__(self): return self.__str__() def main(): ll = LinkedList() num = int(input("Enter a number: ")) while num != -1: ll.addNode(num) num = int(input("Enter a number: ")) c = ll.head while c is not None: print(c.data) c = c.next 

>>> main() Enter a number: 5 Enter a number: 3 Enter a number: 2 Enter a number: 4 Enter a number: 1 Enter a number: -1 1 2 3 4 5 

Answer by Jaylee Norton

In this program, we need to sort the nodes of the given singly linked list in ascending order.,Define a node current which will initially point to the head of the list.,If the list is empty, both head and tail will point to a newly added node.,Continue this process until the entire list is sorted.

 Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9 

Answer by Paislee Moody

To sort a linked list by exchanging data, we need to declare three variables p, q, and end.,The variable p will be initialized with the start node, while end will be set to None.,The Python code for sorting the linked list using bubble sort by exchanging the data is as follows:,We want to merge them in a sorted manner by rearranging the links. To do so we need variables p, q and em. Initially, they will have the following values:

Let’s understand this process with the help of an example. Suppose we have the following list:

In the first iteration, p will be set to 8, and q will be set to 7 . Since p is greater than q , the values will be swapped and p will become p.ref . At this point of time the linked list will look like this:

Since at this point of time, p is not equal to end , the loop will continue and now p will become 8 and q will become 1. Since again p is greater than q , the values will be swapped again and p will again become p.ref . The list will look like this:

Here again, p is not equal to end , the loop will continue and now p will become 8 and q will become 6. Since again p is greater than q , the values will be swapped again and p will again become p.ref . The list will look like this:

The Python code for sorting the linked list using bubble sort by exchanging the data is as follows:

 def bub_sort_datachange(self): end = None while end != self.start_node: p = self.start_node while p.ref != end: q = p.ref if p.item > q.item: p.item, q.item = q.item, p.item p = p.ref end = p 

Let’s take a simple example of how we will swap two nodes by modifying links. Suppose we have a linked list with the following items:

 def bub_sort_linkchange(self): end = None while end != self.start_node: r = p = self.start_node while p.ref != end: q = p.ref if p.item > q.item: p.ref = q.ref q.ref = p if p != self.start_node: r.ref = q else: self.start_node = q p,q = q,p r = p p = p.ref end = p 

At the beginning of the algorithm, p will point to the first element of the list1 whereas q will point to the first element of the list2 . The variable em will be empty. At the start of the algorithm, we will have the following values:

p = 10 q = 5 em = none newlist = none 

After the first comparison we will have the following values:

p = 10 q = 15 em = 5 newlist = 5 

Since q was less than p , therefore, we store the value of q in em moved ‘q’ one index to the right. In the second pass, we will have the following values:

p = 45 q = 15 em = 10 newlist = 5, 10 

Here since p was smaller, we add the value of p to newlist , and set em to p and then moved p one index to the right. In the next iteration we have:

p = 45 q = 35 em = 15 newlist = 5, 10, 15 

Similarly, in the next iteration:

p = 45 q = 68 em = 35 newlist = 5, 10, 15, 35 

And in the next iteration, p will again be smaller than q , hence:

p = 65 q = 68 em = 45 newlist = 5, 10, 15, 35, 45 

p = None q = 68 em = 65 newlist = 5, 10, 15, 35, 45, 65 

When one of the list becomes None , all the elements of the second list are added at the end of the new list. Therefore, the final list will be:

p = None q = None em = 68 newlist = 5, 10, 15, 35, 45, 65, 68 

The Python script for merging two sorted lists is as follows:

 def merge_helper(self, list2): merged_list = LinkedList() merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node) return merged_list def merge_by_newlist(self, p, q): if p.item  

p = 10 q = 5 em = none newlist = none 

p = 10 q = 15 start = 5 em = start 

p = 65 q = 68 em = 45 newlist = 5, 10, 15, 35, 45 

p = None q = 68 em = 65 newlist = 5, 10, 15, 35, 45, 65 

p = None q = None em = 68 newlist = 5, 10, 15, 35, 45, 65, 68 

 def merge_helper2(self, list2): merged_list = LinkedList() merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node) return merged_list def merge_by_linkChange(self, p, q): if p.item  

new_linked_list1 = LinkedList() new_linked_list1.make_new_list() 

How many nodes do you want to create: 4 Enter the value for the node:12 Enter the value for the node:45 Enter the value for the node:32 Enter the value for the node:61 

new_linked_list2 = LinkedList() new_linked_list2.make_new_list() 

How many nodes do you want to create: 4 Enter the value for the node:36 Enter the value for the node:41 Enter the value for the node:25 Enter the value for the node:9 

new_linked_list1. bub_sort_datachange() new_linked_list2. bub_sort_datachange() 

list3 = new_linked_list1.merge_helper2(new_linked_list2)