No.206 反转链表
题目描述
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例 ：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
解题思路
代码实现
# 206. 反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while cur is not None:
# 防止断链
tem = cur.next
# 断开节点链接，将当前节点指针指向前一节点
cur.next = pre
# 同时前移
pre = cur
cur = tem
return preNo.141 环形链表
题目描述
给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。
示例 ：
输入：head = [3,2,0,-4] pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路
代码实现
# 141. 环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if head and head.next is None:
return False
# 初始化快慢指针
fast = head
slow = head
# 当fast指针不空时，进入循环
while fast:
if fast.next and fast.next.next:
fast = fast.next.next # fast 每次前进两步
slow = slow.next # slow 每次前进一步
else:
return False
# fast 总会追上 slow
if (fast == slow):
return True
return FalseNo.21 合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 ：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
解题思路
代码实现
# 21. 合并两个有序链表
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
cur = dummy
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
if l1:
cur.next = l1
else:
cur.next = l2
return dummy.nextNo.19 删除链表的倒数第 N 个结点
题目描述
给你一个链表，删除链表的倒数第
n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解题思路
代码实现
# 19. 删除链表的倒数第 N 个结点
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(-1)
first = head
second = dummy
# 遍历后确定 first 指针的初始位置
for i in range(n):
first = first.next
# 整体后移
while first:
first = first.next
second = second.next
# 删除结点
second.next = second.next.next
return dummy.next错误代码
# 错误：如果目标节点的值提前出现，则会误删
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
pre = dummy
# 寻找目标节点函数
def find(m):
fast = head
slow = head
for i in range(m):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow.val
# 删除找到的节点的值
while pre.next:
if pre.next.val == find(n):
pre.next = pre.next.next
break
pre = pre.next
return dummy.nextNo.876 链表的中间结点
题目描述
给定一个头结点为
head 的非空单链表，返回链表的中间结点.如果有两个中间结点，则返回第二个中间结点。输出1,2,3,5
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
解题思路
代码实现
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
fast = slow = head
# 快慢指针
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow版权属于：KevinBean
本文链接：https://www.kevinbean.top/index.php/default/275.html
转载时须注明出处及本声明