由单链表排序相关的系列问题的总结,相关算法

1. 排序

插入插叙的时间复杂度是O(n^2), 如何保证时间复杂度在O(nlgn)呢。 快速排序可行吗? 归并排序呢?

1.1 插入排序

思路

这应该是最容易想到的一个方法:

class Node(object):
    def __init__(self, val):
        self.next = None
        self.val = val

    def __rper__(self):
        # 迭代的形式
        res = ""
        tmp = self.next
        res += str(self.val)
        while tmp:
            res += "->"
            res += str(tmp.val)
            tmp = tmp.next
        return res

    def rper_good(self):
        # 递归的形式
        if self:
            return "{} -> {}".format(self.val, repr(self.next))



def sort(root):
    Dumy = Node(0)
    Dumy.next = root
    res = Node(0)
    res.next = root

    while Dumy.next:
        pivot = Dumy.next.val
        head = Dumy.next.next
        prev = Dumy.next
        while head:
            next_val = head.val
            if next_val < pivot:
                cur_next = head.next
                head.next = Dumy.next
                Dumy.next = head
                prev.next = cur_next
            prev = head
            head = head.next
        Dumy= Dumy.next
    return res.next

if __name__ == "__main__":
    root = Node(0)
    root.next = Node(2)
    root.next.next = Node(3)
    root.next.next.next = Node(1)
    root.next.next.next.next = Node(4)
    import time
    s = time.time()

输出

0->2->3->1->4
0->1->2->3->4
cost 0.00022602081298828125

但是这种方法在lc上会出现超时,因为算法复杂度是O(n^2)

1.2 归并排序

核心思想的第一步需要把链表分割成两个一组。 然后再进行merge。

对于数组而言的话,分割是很容易的,因为可以根据长度按照索引找到中间的位置,对于链表的话,怎么做到这一点呢?

通过快慢指针吗?

  class Solution(object):
      def sortList(self, root):
          """
          :type head: ListNode
          :rtype: ListNode
          """
          # 首先边界条件判断
          if (root is None) or (root.next is None):
              return root
          fast = root
          slow = root

          while fast.next is not None and fast.next.next is not None:
              fast = fast.next.next
              slow = slow.next

          # 当上一步结束的时候,slow正好在中间位置,则断开上述链表
          fast = slow
          slow = slow.next
          fast.next = None

          L1 = self.sortList(root)
          L2 = self.sortList(slow)

          return self.mergeTwoLists(L1,L2)


      def mergeTwoLists(self, L1, L2):
          dumpy = ListNode(0)
          p = dumpy
          while L1 != None or L2 != None:
              if L1 is None:
                  p.next = L2
                  # 如果return的是p这个地方就会有问题,所以要多注意返回的应该是最开始的那个头的地址,而不是p
                  return dumpy.next
              elif L2 is None:
                  p.next = L1
                  return dumpy.next
              elif L1.val < L2.val:
                  p.next = L1
                  L1 = L1.next
              else:
                  p.next = L2
                  L2 = L2.next
              p = p.next
          return dumpy.next

2. 有序链表删除重复

Given a sorted linked list,
delete all duplicates such that each element appear only once.

Example
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

def remove(head):
    if head is None or head.next is None: return head
    dumpy = ListNode(0)
    dumpy.next = head
    while head is not None:
        cur = head.next
        while cur is not None and head.val == cur.val:
            cur = cur.next
            head.next = cur # notice this point, not cur.next
        print head.val
        head = head.next
    return dumpy

head = ListNode(1)
head.next = ListNode(1)
head.next.next = ListNode(1)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(3)

return remove(head)

0 -> 1 -> 2 -> 3 -> None

3. 有序链表删除重复II

Given a sorted linked list, delete all nodes that have duplicate numbers,
leaving only distinct numbers from the original list.

Example
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

def remove(head):

    if head is None or head.next is None: return head
    dumpy = ListNode(0)
    prev = dumpy
    cur = head
    while cur:
        if cur.next is not None and cur.val == cur.next.val:
            val = cur.val
            while cur and val == cur.val:
                cur = cur.next
            prev.next = cur
        else:
            prev.next = cur
            prev = cur
            cur = cur.next

    return dumpy.next

head = ListNode(1)
head.next = ListNode(1)
head.next.next = ListNode(1)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(3)

return remove(head)

2 -> 3 -> None

4. linked list cycle

需要两个指针,一个快指针,一个慢指针。 加入两个指针相遇的话,则说明有换,如果慢指针走完了所有的路线, 没有出现相遇的场景,则说明这个链表其实是没有环的。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None: return False

        slow = head.next
        fast = head.next.next
        while slow:
            if slow == fast:
                return True
            else:
                slow = slow.next
                falst = fast.next.next
        return False

None