Leetcode【24、109、328、455、725】
Leetcode【24、109、328、455、725】
问题描述：【Linked List、Recursion】24. Swap Nodes in Pairs
解题思路：
这道题是给一个链表，相邻结点数值两两进行交换，要求不修改结点值且只能操作链表本身。
方法1：三指针完成交换
链表中一般涉及两个结点交换的操作，基本上需要相邻的三个指针 pre1，pre2，cur 完成三次交换操作，然后再移动三个指针到下一个正确的位置。 因此，我们只需要循环 cur 的位置，往后一直遍历直到链表为空为止。
在这道题中，因为是两两交换，所以方便的解法就是建立一个空给点 node，作为链表的头结点 head，最后返回的 head.next 就是答案。
注意在交换的过程中，每次交换的三个操作要保证链表不能断。
时间复杂度 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 swapPairs(self, head: ListNode) -> ListNode:
if head == None or head.next == None: return head
node = ListNode(-1) # 头部插入一个空结点
node.next = head
head = node
# 三指针法
pre2, pre1, cur = head, head.next, head.next.next
while cur:
pre2.next = cur # 交换
pre1.next = cur.next
cur.next = pre1
pre2 = pre1 # 修改
pre1 = pre1.next
if pre1 == None: break # 防止pre1.next为空
cur = pre1.next
return head.next方法2：递归
这道题实际上还可以使用递归（只不过不太好想，看了别人的代码才恍然大悟）。
1、函数的返回值：交换后的链表的头结点 head。 2、递归函数做了什么：假设 1->2->3->4->5->...，递归函数完成了 3->4->5... 的交换 swapPairs(head.next.next)，并返回了指向 4 的 head，因此需要建一个 second 指向 2，然后将 head.next 指向递归函数的返回值，并将 second 作为头结点 head，最后返回 second。 3、递归出口：如果链表为空或者 head.next 为空，就之间返回 head。
总之，你不用去想递归函数 swapPairs() 后面的交换是怎么完成的，只需要知道它能够完成交换即可（或许这就是递归的精髓吧）。
时间复杂度 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 swapPairs(self, head: ListNode) -> ListNode:
if head == None or head.next == None: # 递归出口
return head
second = head.next
head.next = self.swapPairs(head.next.next)
second.next = head
return second问题描述：【Linked List、Tree】109. Convert Sorted List to Binary Search Tree
解题思路：
这道题是给一个有序链表，将其转化为高度平衡的二叉搜索树。
要将有序链表转化为高度平衡的二叉搜索树，就需要从链表的中间断开，然后对于左右链表就行递归调用即可。具体细节：
1、链表查找中间点可以通过快慢指针来操作。 2、找到中点后，要以中点的值建立一个树的根结点，再把原链表断开，分为前后两个链表，都不能包含原中结点，然后再分别对这两个链表递归调用原函数，分别连上左右子结点即可。
时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head == None:
return None
if head.next == None:
return TreeNode(head.val)
pre = None # 记录 slow 的前一个结点，便于断开左右链表
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None # 从中间断开
node = TreeNode(slow.val)
node.left = self.sortedListToBST(head) # [head, slow-1] 左区间
node.right = self.sortedListToBST(slow.next) # [slow+1,] 右区间
return node问题描述：【Linked List】328. Odd Even Linked List
解题思路：
这道题是给一个链表，将奇数位置的数按位置顺序排在链表前面，偶数位置的数按位置顺序排在链表后面。要求空间复杂度 O(1)，时间复杂度 O(n)。
设置三个指针，一个指向奇数尾部的指针 p，一个指向当前结点 cur，一个指向当前结点的前一个结点 pre。遍历 cur 的过程中交换三个指针的指向，然后再移动它们到下一个正确的位置即可。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if head == None: return None
p = pre = head # p: 奇数尾结点, pre: cur的前一个结点
cur = head.next # 当前结点
while cur:
pre = pre.next
cur = cur.next
if cur == None: # 防止后面交换的时候cur没有next域
break
pre.next = cur.next # 交换
cur.next = p.next
p.next = cur
p = p.next # 下一次交换做准备
cur = pre.next
return head问题描述：【Linked List】445. Add Two Numbers II
解题思路：
这道题是给两个链表，将两个链表相加。
使用了一种简单的做法，就是将两个链表的值保存在 list 中，然后反向遍历 list，利用头插法构造新链表，将每次计算的各个位的结果保存在新链表中即可。这样时间复杂度和空间复杂度均为 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 addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
list1, list2 = [], []
head1, head2 = l1, l2
while head1:
list1.append(head1.val)
head1 = head1.next
while head2:
list2.append(head2.val)
head2 = head2.next
i, j, c = len(list1) - 1, len(list2) - 1, 0 # c:进位
head = None
while i >= 0 or j >= 0 or c == 1:
add = c
if i >= 0: add += list1[i]
if j >= 0: add += list2[j]
c = add // 10
node = ListNode(add % 10)
node.next = head # 头插法
head = node
i, j = i - 1, j - 1
return head问题描述：【Linked List】725. Split Linked List in Parts
解题思路：
这道题是给一个链表和整数 k，将链表划分成长度尽可能相等的 k 个连续部分，返回链表列表。
首先需要注意，链表列表是指一个列表，列表中每一项是一个链表。这道题根据链表的长度 size （先遍历一次链表）分为两种情况：
1、size <= k：每段链表只有一个值或者为 None。
2、size > k：通过 div, mod = divmod(size, k) 来计算每段链表中至少应该包含 div 个值，然后将 mod 平均分配到前面每一段链表中。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
cur = root
size = 0 # 链表长度
while cur:
size += 1
cur = cur.next
ans = [] # 结果
if size <= k:
cur = root
for i in range(k):
if i < size:
ans.append(ListNode(cur.val))
cur = cur.next
else:
ans.append(None) # 空链表
else:
div, mod = divmod(size, k)
for _ in range(k): # 对于每一段
head = cur = root # head 构造每一段链表
for _ in range(div - 1): # 注意少循环一次，防止 cur.next 越界
cur = cur.next
if mod > 0: # 有余数，平均分配到前面每一段链表中
cur = cur.next
mod -= 1
root = cur.next # root 指向剩余的链表
cur.next = None # 截断
ans.append(head) # 将每一段链表保存
return ans