# Leetcode【24、109、328、455、725】

##### 解题思路：

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:
node = ListNode(-1)  # 头部插入一个空结点
# 三指针法
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

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:
return second```
##### 解题思路：

1、链表查找中间点可以通过快慢指针来操作。 2、找到中点后，要以中点的值建立一个树的根结点，再把原链表断开，分为前后两个链表，都不能包含原中结点，然后再分别对这两个链表递归调用原函数，分别连上左右子结点即可。

##### 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:
return None
pre = None  # 记录 slow 的前一个结点，便于断开左右链表
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None # 从中间断开
node = TreeNode(slow.val)
node.right = self.sortedListToBST(slow.next)  # [slow+1,] 右区间
return node```

##### 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的前一个结点
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

##### 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 = [], []
i, j, c = len(list1) - 1, len(list2) - 1, 0  # c:进位
while i >= 0 or j >= 0 or c == 1:
if i >= 0: add += list1[i]
if j >= 0: add += list2[j]
i, j = i - 1, j - 1
##### 解题思路：

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):  # 对于每一段
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  # 截断
return ans```

0 条评论

• ### Leetcode【61、82、83、142、143、1171】

1、先计算链表长度 size，k = k % size，如果 k % size == 0，则不用移动，直接返回 head； 2、否则，需要将前 size - ...

• ### Q83 Remove Duplicates from Sorted List

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

• ### Leetcode【86、92、148、206】

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

• ### Leetcode【61、82、83、142、143、1171】

1、先计算链表长度 size，k = k % size，如果 k % size == 0，则不用移动，直接返回 head； 2、否则，需要将前 size - ...

• ### LEETCODE - Linked List 题目思路汇总

浏览了一下 Leetcode 上 Linked List 的题目，我把它分为 6 类： 调换顺序 删除 合并 环 变身 复制 做Leetcode还是要归类总结才...

• ### 插入排序

周末又到啦！各位小伙伴周末愉快哈！随着刷题的数量的增多，慢慢感觉到很多题目之间的内在关联，每周遇到的比较新奇的题目还是坚持与各位分享一下~

• ### 用最容易的方式学会单链表（Python实现）

在本博客中，我们介绍单链表这种数据结构，链表结构为基于数组的序列提供了另一种选择（例如Python列表）。

• ### 「复制带随机指针的链表」的一个很巧妙解法

题目来源于 LeetCode 上第 138 号问题：复制带随机指针的链表。题目难度为 Medium，目前通过率为 40.5% 。

• ### 实践 -实现一款中间凸起的TabBar

这是看到一篇文章后感觉很有意思于是就把自己的效果改了改实现了一下，文末有原文链接。