- 来源于leetcode题库
2,19,142,148 - 链表问题一般可用
快慢指针解决 - 子串问题一般用
滑动窗口解决
2.两数相加
- 题目描述：
- 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
- 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
- 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
- 示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
- 题解：
# 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:
dummy = p = ListNode(None)
s = 0
#l1或l2不为空或s不等于0
while l1 or l2 or s:
#简写形式，因为是逆序，所以链表的首位是个位
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
#个位数的和对10取余，得到相加后链表对个位数放入链表
p.next = ListNode(s % 10)
#链表后移到下一个节点
p = p.next
#个位数对和对10整除，得到需要进位的数
s //= 10
#两个相加的链表也移动到下一个节点，对下一位进行相加
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
#返回队首的节点
return dummy.next
19.删除链表的倒数第n个节点
- 题目描述：
- 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
- 示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
- 题解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
'''
使用双指针的解法
快指针先走n步，然后快慢指针同时向前移动
如果快指针的后续节点为空，则慢指针已经到达被删除节点的前置节点
'''
if not head:
return head
slownode = ListNode(None)
slownode.next = head
fastnode = slownode
#快指针先走n步
for i in range(n):
fastnode = fastnode.next
while(fastnode.next != None):
slownode = slownode.next
fastnode = fastnode.next
if slownode.next == head:
head = head.next
else:
slownode.next = slownode.next.next
return head
142.环形链表二
-
题目描述
- 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
- 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
-
示例
image.png 题解
题解来源于题解区大佬
Krahets，如有侵扰烦请联系删除
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
'''
1.fast,slow指向head，fast走2步，slow走1步，fast是slow的2倍
2.第一次相遇：
2.1 fast走过链表末端，则没有环
2.2 fast == slow 第一次相遇，假如有a+b个节点，头部为a个，环内为b个，
两指针分别走了f，s步
fast走的是slow的2倍，f=2s
fast比slow多走了n个环的长度，f=s+nb
可得f=2nb , s=nb ,即fast,slow分别走了2n,n个环的周长
指针从头部走到入口节点的所有步数情况为k=a+nb
slow走了nb部，只要再走a步就能到入口
链表头部与slow同步走a步就可以一起到入口节点
3.第二次相遇
3.1 slow位置不变，fast重新指向链表头部，fast与slow同时每轮走1步
此时f=0 s=nb
3.1 fast走到f=a时，slow为s=a+nb，此时指针重合并指向入口
'''
#初始双指针
fast, slow = head, head
#第一次相遇
while True:
if not (fast and fast.next):
return
#快指针走2步，慢指针走1步
fast, slow = fast.next.next, slow.next
if fast == slow:
break
#第二次相遇
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
#返回入口位置
return fast
148 排序链表
- 题目描述
- 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
- 示例
输入: 4->2->1->3
输出: 1->2->3->4
- 题解
# 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
slow,fast = head,head.next
while fast and fast.next:
fast,slow = fast.next.next,slow.next
mid,slow.next = slow.next,None
left,right = self.sortList(head),self.sortList(mid)
h = res = ListNode(0)
while left and right:
if left.val < right.val:
h.next,left = left,left.next
else:
h.next,right = right,right.next
h = h.next
h.next = left if left else right
return res.next
