leetcode链表之反转链表
2022-03-22 本文已影响0人
小奚有话说
本文主要有三道题，都是关于反转链表的算法题，由浅入深。
文章出现的代码都是python3
206、反转链表
题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例2：
输入：head = [1,2]
输出：[2,1]
示例3：
输入：head = []
输出：[]
思路
记录当前结点和上一个结点，然后将当前结点的指针指向上一个结点
代码：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, cur = None, head
while cur:
# 存储当前结点的下一个结点，避免结点丢失
next = cur.next
# 将当前结点的指针反转指向上一个结点
cur.next = prev
# 将prev移动到cur，并将cur移动到下一个结点，进行下一次循环
prev = cur
cur = next
return prev
92、反转链表2
题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例2：
输入：head = [5], left = 1, right = 1
输出：[5]
思路
查找到左右两个结点，单独对这两个结点之间的链表进行反转，将翻转后的结果拼接到原来的链表中。
需要注意保留左节点的前一个结点，用于左节点的拼接
代码：
class Solution:
# 反转头结点到尾结点之间的链表，并返回新的头结点和尾结点
def reversed(self, head, tail):
prev, cur = None, head
t = head
while cur:
next = cur.next
cur.next = prev
prev = cur
if cur == tail: break
cur = next
return prev, t
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
if not head or not head.next: return head
vHead = ListNode(0, head)
cur = vHead
# 移动left-1的距离，到达左结点的前一个结点，用于左链表的拼接
for i in range(left - 1):
cur = cur.next
preLeft = cur
# 由于是从左节点的前一个结点进行遍历，所以右节点的遍历需要+1
for i in range(right - left + 1):
cur = cur.next
rightNode = cur
nextRight = rightNode.next
# 进行左右结点链表反转
bHead, bTail = self.reversed(preLeft.next, rightNode)
# 进行链表的拼接
preLeft.next = bHead
bTail.next = nextRight
return vHead.next
25、K个一组翻转链表
题目
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例4：
输入：head = [1], k = 1
输出：[1]
思路
这个问题主要有两个点，1个是k个结点，2是进行翻转
k个结点可以使用快慢结点来解决
class Solution:
# 翻转链表，
# 1、先将next结点保存起来，更改当前结点的指向，即将当前结点指向前一个结点
# 2、然后向后移动结点
# 需要考虑边界值，当翻转过后，判断当前结点是不是已经到尾部了，此时可以结束循环
def reversed(self, head, tail):
prev, cur = None, head
t = head
while cur:
next = cur.next
cur.next = prev
prev = cur
if cur == tail: break
cur = next
return prev, t
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or k == 1: return head
vHead = ListNode(0, head)
cur = vHead
fast = head
while fast:
# 快结点每次先移动k个距离，如果距离不够，则直接返回即可
for i in range(k-1):
fast = fast.next
if not fast: return vHead.next
# 此时要保存一下快结点的下一个结点，避免链表结点信息丢失
fnext = fast.next
prev, tail = self.reversed(cur.next, fast)
# 将翻转之后的头结点拼接起来
cur.next = prev
tail.next = fnext
# 将当前结点移动至翻转后的尾结点处，快指针移到下一个结点，进行下一次循环
cur = tail
fast = fnext
return vHead.next
