所谓链表，就是由链节点元素组成的表，那什么是链节点呢？直接上定义：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
很简单，链节点就是只记录自身的值 val，还有其指向的下一个链节点的位置 next。
707. 设计链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MylinkedList:
def __init__(self):
self.size = 0
self.head = ListNode(0)
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
curr = self.head
# 找到查找的位置
for _ in range(index + 1):
curr = curr.next
return curr.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
if index < 0:
index = 0
# size加一，并且找到插入位置
self.size += 1
pred = self.head
for _ in range(index):
pred = pred.next
# 插入节点三步走：新建节点，新节点指向下一个节点，新节点被上一个节点指向
to_add = ListNode(val)
to_add.next = pred.next
pred.next = to_add
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
# size减一，并且找到删除位置
self.size -= 1
pred = self.head
for _ in range(index):
pred = pred.next
# 直接跳过节点即为删除
pred.next = pred.next.next
由链节点出发，设计单链表的思路如下：初始化的时候，要新建一个头节点 head（即第一个节点），同时为了方便要记录链表的大小 size。然后就是三种操作：查找、插入和删除。
查找：首先判断索引是否越界，越界就返回 -1，不越界才继续。从头节点开始，根据链节点 的 next 找到其下一个节点，循环 index 次找到目标节点，返回其值。
插入：同样先判断是否越界。不越界则可以插入，此时链表的大小 size 会 +1，接着循环 index 次找到目标节点（插入位置），然后是插入三步走：新建节点，新节点指向下一个节点，新节点被上一个节点指向。对于从头部、中间、尾部插入都一样，只是位置不同而已。
删除：同样先判断是否越界。不越界则可以删除，此时链表的大小 size 会 -1，接着循环 index 次找到目标节点（删除位置），然后直接跳过此节点 next = next.next，即为删除。
剑指 Offer 22. 链表中倒数第k个节点（面试题 02.02. 返回倒数第 k 个节点）
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
nums = []
while head:
nums.append(head)
head = head.next
return nums[-k]
遍历链表，返回倒数第k个节点的值。
剑指 Offer 06. 从尾到头打印链表
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
nums = []
while head:
nums.append(head.val)
head = head.next
return nums[::-1]
遍历链表，倒序返回链表所有的值。
876. 链表的中间结点
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
all_nodes = []
while head:
all_nodes.append(head)
head = head.next
return all_nodes[len(all_nodes) // 2]
遍历链表，记录链节点，然后返回中间那个。当然，更好地是用快慢指针，慢指针每次移到next，快指针每次移到 next 的 next，循环结束返回慢指针即为中间节点。
141. 环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
slow, fast = head, head
while slow.next and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
快慢指针更典型的例子是环形链表，如果链表是有环的，则快指针一定会从后面追上慢指针，否则它们不会相遇。
142. 环形链表 II（剑指 Offer II 022. 链表中环的入口节点）（面试题 02.08. 环路检测）
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow, fast = head, head
flag = False
while slow.next and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
flag = True
break
if not flag:
return None
ans = head
while ans != slow:
ans = ans.next
slow = slow.next
return ans
这题不仅要判断是否环形，还要找出入环点，作图分析快慢指针相遇时头节点到入环点的距离，以及入环点到相遇点的距离关系即可得出答案。
160. 相交链表（剑指 Offer II 023. 两个链表的第一个重合节点）（面试题 02.07. 链表相交）
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
curA = headA
curB = headB
while curA != curB:
curA = curA.next if curA else headB
curB = curB.next if curB else headA
return curA
同样是双指针思路（非快慢），分别从两个链表同时出发，遍历完一个链表就去遍历另一个链表，如果链表相交，则两个指针一定相遇于交点，否则同时为 None。
61. 旋转链表
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return None
cur = head
length = 1
while cur.next:
cur = cur.next
length += 1
cur.next = head
new_tail = head
for _ in range(length - k % length - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
这题把链表变成环形之后，找到目标切分点即可。
203. 移除链表元素（剑指 Offer 18. 删除链表的节点）
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
设置一个虚拟头节点 dummy_head，然后判断 cur.next 是否是目标值，如果是则删除（cur.next 指向 cur.next.next），如果不是则移动到 cur.next，循环判断 cur.next。最后返回虚拟头节点的 next ，即真正的头节点。
237. 删除链表中的节点（面试题 02.03. 删除中间节点）
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
题目给出要删除的中间节点 node 而不是头节点，那就把该节点 node 变成其下一个节点 node.next，然后删除下一个节点即可。
83. 删除排序链表中的重复元素
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
cur = head
while cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
删除排序链表中的重复元素，判断当前节点与下一个节点是否相等即可。
面试题 02.01. 移除重复节点
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if not head:
return head
nums = {head.val}
cur = head
while cur.next:
if cur.next.val in nums:
cur.next = cur.next.next
else:
nums.add(cur.next.val)
cur = cur.next
return head
与上一题相比，链表不是有序的，所以得用哈希表（集合）记录出现过的元素，后面如果再次出现则删除。
19. 删除链表的倒数第 N 个结点
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy_head = ListNode(next=head)
first = head
second = dummy_head
for i in range(n):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy_head.next
删除链表的倒数第 n 个节点，用双指针法，第一个指针先遍历 n 次，然后两个指针一起遍历，这样当第一个指针遍历完之后，第二个指针正好遍历了（链表长度 - n）次，其位置即为要删除的位置。
206. 反转链表（剑指 Offer 24. 反转链表）（剑指 Offer II 024. 反转链表）
迭代法
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next # 把下个指针记到 temp
cur.next = pre # cur 的 next 指针反过来指向 pre
pre = cur # 已反向的 cur 变为 pre
cur = temp # cur 向右移一位
return pre
使用前一个节点 pre 和当前节点 cur。在节点 cur 时，先把下个指针记到 temp，然后 cur 的 next 指针反过来指向 pre，已反向的 cur 变为 pre，然后 cur 向右移一位，直到链表结束。在写法上，可以发现变量是头尾相连的，以此作为记忆。
递归法
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
cur = self.reverseList(head.next) # 找到链表尾部
head.next.next = head # 把下个节点的 next 指针指向自己
head.next = None # 删掉自己指向下个节点的 next
return cur
先找到链表尾部，然后从尾部开始把下个节点的 next 指针指向自己，同时删掉自己指向下个节点的 next，递归返回前一个节点，直到遇到空节点为止（从尾部到头部）。
92. 反转链表 II
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
dummy_head = ListNode(-1)
dummy_head.next = head
pre = dummy_head
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
temp = cur.next # temp一定是cur的next
cur.next = temp.next # 让cur指向后两位
temp.next = pre.next # temp指向头后一位
pre.next = temp # 头后一位变为temp
return dummy_head.next
这题要求反转链表中的某一段，头插法是很不错的解法，思路详细看这篇题解。大概就是说，找到要反转的区域，然后遍历其中的元素，每次都把元素移动到区域的最前面（头插），这样遍历完整个区域，也就完成了反转。pre 恒为区域外左边第一个节点，然后是 cur 和 temp（cur.next），每次遍历都会把 temp 送到 pre 的右边（即区域的最前面）。
2. 两数相加（面试题 02.05. 链表求和）
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
remaining = l1.val + l2.val
head = ListNode(remaining % 10)
node = head
remaining = remaining // 10
while l1.next or l2.next:
l1 = l1.next or ListNode(0) # 考虑到了不等长的情况
l2 = l2.next or ListNode(0)
remaining += l1.val + l2.val
node.next = ListNode(remaining % 10) # 构建新的节点
node = node.next # 移到新节点
remaining = remaining // 10 # 商数只取十分位
if remaining: # 最后的商数，构建最后的新节点
node.next = ListNode(remaining)
return head
两个链表对应位置相加，不等长的话短的那个加0，余数作为结果链表的新节点，而商数除以10后作为下一位的加数之一，最后还有一个商数不要漏了。
445. 两数相加 II
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
head = None
carry = 0
while s1 or s2 or carry != 0:
a = 0 if not s1 else s1.pop()
b = 0 if not s2 else s2.pop()
cur = a + b + carry
carry = cur // 10
cur %= 10
curnode = ListNode(cur)
curnode.next = head
head = curnode
return head
这题的两数相加是正序的，做三次反转链表也可以。此处用的是两个栈，注意输出也得是正序，所以链表是从尾部开始生成的，head 每次移动到新节点，直到结束才知道 head 。
234. 回文链表（剑指 Offer II 027. 回文链表）（面试题 02.06. 回文链表）
回文链表最简单的思路是遍历链表，用数组记录所有元素，然后判断数组正序是否等于逆序即可。更好的方法是使用快慢指针，如下：
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head:
return True
# 找到前半部分链表的尾节点并反转后半部分链表
first_half_end = self.end_of_first_half(head)
second_half_start = self.reverse_list(first_half_end.next)
# 判断是否回文
result = True
first_position = head
second_position = second_half_start
while result and second_position:
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next
# 还原链表并返回结果
first_half_end.next = self.reverse_list(second_half_start)
return result
def end_of_first_half(self, head): # 找到链表的中间
fast = head
slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow
def reverse_list(self, head): # 反转链表
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
思路很简单，首先是用快慢指针找到链表的中间位置，然后把后半部分的链表反转，接着就可以逐一判断前后两部分的元素是否相等，用 result 进行记录，最后再把后半部分链表反转回去（不改变链表结构）。
21. 合并两个有序链表（剑指 Offer 25. 合并两个排序的链表）
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
cur = head
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return head.next
合并两个有序的链表，方法就是新建一个节点 head，迭代进行：如果两个链表都非空，就让新链表指向数值小的节点，然后移动下一位，直到其中一个链表为空，则把另一个链表作为新链表剩下的部分。
86. 分隔链表（面试题 02.04. 分割链表）
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
if not head:
return head
small = ListNode(0)
small_head = small
large = ListNode(0)
large_head = large
while head:
if head.val < x:
small_head.next = head
small_head = small_head.next
else:
large_head.next = head
large_head = large_head.next
head = head.next
large_head.next = None
small_head.next = large.next
return small.next
这题思路不难，就是用 small 和 large 两个链表分别记录比 x 小和比 x 大（或等）的节点，然后 small 拼接上 large，large 末尾指向 None 即可。
328. 奇偶链表
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head:
return head
evenHead = head.next
odd, even = head, evenHead
while even and even.next:
odd.next = even.next # 节点1指向节点3
odd = odd.next # 节点1移动到节点3
even.next = odd.next # 节点2指向节点4
even = even.next # 节点2移动到节点4
odd.next = evenHead # 最后一个奇节点指向第一个偶节点
return head
这题固然也可以像上一题那样，开两个链表来记录，但是麻烦了。由于都在同一个链表中，所以直接两两改变链接就行了。
143. 重排链表（剑指 Offer II 026. 重排链表）
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return
l1 = head
middle_node = self.middleNode(head)
l2 = middle_node.next
middle_node.next = None
l2 = self.reverseNode(l2)
self.mergeList(l1, l2)
def middleNode(self, head: ListNode) -> ListNode:
slow, fast = head, head
while slow.next and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseNode(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def mergeList(self, l1: ListNode, l2: ListNode) -> ListNode:
while l1 and l2:
l1_temp = l1.next
l2_temp = l2.next
# 让l1指向l2，l2指向l1.next，即摆动了两个指针，然后都移动到下一位
l1.next = l2
l1 = l1_temp
l2.next = l1
l2 = l2_temp
此题思路可以分为三步走：
1、找到原链表的中点（876. 链表的中间结点）
2、将原链表的右半端反转（206. 反转链表）
3、将原链表的两端合并（21. 合并两个有序链表）
