LeetCode: 147. Insertion Sort List

题目

原题地址：https://leetcode.com/problems/insertion-sort-list/

Sort a linked list using insertion sort.

image

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

解法

生成一个有序数组，然后再生成结果链表

简单来说就是，先遍历链表生成一个有序数组，然后再基于这个数组生成所需的链表。

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head):
        nodes = []
        while head is not None:
            self.insert_node(nodes, head)
            head = head.next

        dummy = ListNode()
        tail = dummy
        for node in nodes:
            tail.next = node
            tail = node
        # 防止节点上原有的 next 属性值导致出现循环
        tail.next = None

        return dummy.next

    def insert_node(self, nodes, node):
        for i, v in enumerate(nodes):
            if node.val < v.val:
                nodes.insert(i, node)
                break
        else:
            nodes.append(node)

        return nodes

不生成中间数组，直接对链表进行排序操作

可以省略中间数组，在对链表进行遍历的过程中按照上面数组类似的逻辑进行排序。

  • 定义一个空链表 dummy ，作为排序后的结果链表，类似上面的中间数组
  • 遍历输入的链表，将节点插入到上面的 dummy 链表中，为了保持 dummy 有序，需要按上面类似 insert_node 的方法在 dummy 中找到合适的位置，因为 dummy 是个链表而不是数组无法直接插入，需要记录插入位置的上一个节点 (pre_node) 和下一个节点(next_node)，然后再基于这两个节点的信息实现插入新节点的功能。

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def insertionSortList(self, head):
        # 新的链表
        dummy = ListNode()

        current = head
        while current is not None:
            # 把 current 插入到 dummy 链表中
            # 新节点插入位置的上一个节点
            pre_node = dummy
            # 新节点插入位置的下一个节点
            next_node = pre_node.next
            while next_node is not None:
                # 找到插入位置
                if current.val < next_node.val:
                    break
                pre_node = next_node
                next_node = next_node.next
            # 插入新节点
            pre_node.next = current
            _next = current.next
            current.next = next_node
            current = _next

        return dummy.next

Comments