Leetcode【86、92、148、206】

  • 2019 年 10 月 29 日
  • 筆記

问题描述:【Linked List】86. Partition List 解题思路:

这道题是给一个链表和整数 x,将小于 x 的数按位置顺序放在链表左侧,大于等于 x 的按位置顺序放在右侧。

类似于快排的划分过程有木有。可以建立两个指针 l_end 和 r_end,分别指向 x 的左右两部分的尾部。再建立一个指针指向当前结点 cur,便于链表的遍历。因为我们不知道第一个结点和 x 的关系,所以可以建一个空结点 node 指向 head,最后 head.next 就是答案。

  • l_end 初始化为 head(空结点),r_end 初始化为 None,cur 指向 head.next 第一个结点;
  • 遍历 cur: 1、如果 cur.val < x and r_end == None,说明刚开始碰到的都是小于 x 的,就只需要移动 l_end 到 cur 的位置即可; 2、 如果 cur.val < x,这个时候 r_end 不为空,利用这三个指针进行交换和移动即可; 3、否则,碰到的都是大于等于 x 的,就只需要移动 r_end 到 cur 的位置即可。

时间复杂度为 O(n),空间复杂度为 O(1)。

Python3 实现:
# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def partition(self, head: ListNode, x: int) -> ListNode:          node = ListNode(-1)  # 头结点          node.next = head          head = node          l_end, r_end, cur = head, None, head.next          while cur:              if cur.val < x and r_end == None:  # 没遇到比 x 大的,只移动 l_end                  l_end = cur              elif cur.val < x:  # r_end 不为 None,利用三指针交换                  r_end.next = cur.next  # 交换                  cur.next = l_end.next                  l_end.next = cur                  l_end = cur  # 移动                  cur = r_end              else:                  r_end = cur              cur = cur.next          return head.next

问题描述:【Linked List】92. Reverse Linked List II 解题思路:

这道题是给一个链表和区间 [m, n],反转区间内的数字。

这道题和下面的 Leetcode 206 思路相同。对于一个区间的反转,需要用 notr 记录不用反转区间的最后一个位置;用 start 记录反转区间的头指针;为了反转方便,再定义 pre 和 cur 分别为前一个指针和当前指针。遍历 cur,找到反转区间,进行指针的交换和移动操作即可。

时间复杂度为 O(n),空间复杂度为 O(1)。

Python3 实现:
# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:          if not head:              return head          # notr: 不用反转区间的最后一个位置          # start: 反转区间的头指针          # pre, cur:前一个指针和当前指针          notr, start, pre, cur = None, None, None, head          i = 1          while cur:              if i <= m:                  if i == m:  # 初始化四个指针                      notr = pre                      start = cur                  pre = cur                  cur = cur.next              elif m < i <= n:  # 在起始位置的下一个位置反转,通过指针交换完成                  pre.next = cur.next # 交换                  cur.next = start                  start = cur                  if m == 1:  # 从头开始                      head = cur                  else:  # 从中间开始                      notr.next = start                  cur = pre.next  # 移动              else:                  break              i += 1          return head

问题描述:【Linked List】148. Sort List 解题思路:

这道题是给一个链表,对链表排序。要求时间复杂度 O(nlogn),空间复杂度 O(1)。

首先,肯定能想到要么是使用快速排序,要么是归并排序。刚好上面的 Leetcode 86 为链表划分,所以就借助其思想实现了快排。但是最后一个 case 超时了(嘤嘤嘤),代码如下:

Python3 实现:
# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def sortList(self, head: ListNode) -> ListNode:          if not head or not head.next:  # 递归出口              return head          pivot = head.val          le, ri, cur = head, None, head.next  # 左右区间划分          while cur:              if cur.val < pivot and ri == None:                  le = cur              elif cur.val < pivot:                  ri.next = cur.next  # 交换                  cur.next = le.next                  le.next = cur                  le = cur  # 移动                  cur = ri              else:                  ri = cur              cur = cur.next          ri = le.next  # 左右两侧排序          le.next = None          lp = self.sortList(head.next)          rp = self.sortList(ri)          if lp == None:   # 将基准 head.val 放到中间              head.next = rp              lp = head          else:              cur = lp              while cur.next:                  cur = cur.next              cur.next = head              head.next = rp          return lp  # 返回链表头结点

看了题解,有人使用归并排序 mergeSort 通过了,同样可以做到时间复杂度为 O(nlogn),空间复杂度为 O(1)。代码如下(不是我写的,懒得再写一次了):

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def sortList(self, head: ListNode) -> ListNode:          if head is None:              return None          p, i = head, 0          while p:              i += 1              p = p.next          return self.mergeSort(head, i)[0]        def mergeSort(self,head,k):          if k == 1:              next = head.next              head.next = None              return head, next          left_head, next = self.mergeSort(head, k//2)          right_head, next = self.mergeSort(next, k-(k//2))          return self.merge(left_head, right_head), next        def merge(self, h1, h2):          dummy = ListNode(0)          p = dummy          while h1 and h2:              if h1.val <= h2.val:                  p.next = h1                  p = p.next                  h1 = h1.next              else:                  p.next = h2                  p = p.next                  h2 = h2.next          if h1 is None and h2 is not None:              p.next = h2          elif h2 is None and h1 is not None:              p.next = h1          return dummy.next

问题描述:【Linked List】206. Reverse Linked List 解题思路:

这道题是给一个链表,将链表反转。

链表反转只需要两个相邻指针 pre 和 cur 即可。对于 cur 遍历,先交换(3 次操作)后移动指针到正确的位置,时间复杂度为 O(n)。

Python3 实现:
# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def reverseList(self, head: ListNode) -> ListNode:          if not head:              return head          pre, cur = head, head.next          while cur:              pre.next = cur.next  # 交换              cur.next = head              head = cur              cur = pre.next  # 移动          return head