25. K 个一组翻转链表
题目
给你一个链表, 每 k 个节点一组进行翻转, 请你返回翻转后的链表.
k 是一个正整数, 它的值小于或等于链表的长度.
如果节点总数不是 k 的整数倍, 那么请将最后剩余的节点保持原有顺序.
示例:
给你这个链表: 1->2->3->4->5
当 k = 2 时, 应当返回: 2->1->4->3->5
当 k = 3 时, 应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间.
你不能只是单纯的改变节点内部的值, 而是需要实际进行节点交换.
解题思路
思路: 迭代, 翻转链表
具体思路:
首先要确保翻转的范围, 这个是由题目中提及的 k 来控制;
关于链表的翻转, 要注意前驱和后继的问题, 防止指向错误, 这里也为了将翻转后的链表与后续进行连接;
定义 pre 和 tail,pre 表示待翻转链表部分的前驱, tail 表示末尾;
上面的 tail 经由 k 控制到达末尾;
翻转链表, 将翻转后的部分与后续进行拼接;
注意: 根据题意, 当翻转部分的长度小于 k 时, 这个时候不做处理.
具体的代码实现如下.
代码实现
- # Definition for singly-linked list.
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
- if head == None and head.next == None and k <2:
- return head
- # 定义哨兵节点
- dummy = ListNode(0)
- # 指向节点
- dummy.next = head
- # 定义前驱后继节点
- pre = dummy
- tail = dummy
- # 控制 tail 到待翻转链表部分的末尾
- while True:
- count = k
- while count> 0 and tail != None:
- count -= 1
- tail = tail.next
- # 到达尾部时, 长度不足 k 时, 跳出循环
- if tail == None:
- break
- # 这里用于下次循环
- head = pre.next
- # 开始进行翻转
- while pre.next != tail:
- tmp = pre.next
- pre.next = tmp.next
- tmp.next = tail.next
- tail.next = tmp
- # 重置指针
- pre = head
- tail = head
- return dummy.next
实现结果
以上就是使用迭代, 根据题目提供的 k 值确定翻转链表部分, 在内部实现翻转, 进而解决《25. K 个一组翻转链表》的主要内容. 其中注意要定义链表的前驱和后继, 防止指向错误.
来源: https://www.cnblogs.com/yiluolion/p/12823002.html