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