网站开发倒计时,南宁seo团队计划,wordpress用户系统,最新国际军事新闻头条新闻基础知识要求#xff1a; Java#xff1a;方法、while循环、for循环、if else语句 Python#xff1a; 方法、while循环、for循环、if else语句 题目#xff1a;
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。
k 是一个…基础知识要求 Java方法、while循环、for循环、if else语句 Python 方法、while循环、for循环、if else语句 题目
给你链表的头节点 head 每 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]提示
链表中的节点数目为 n1 k n 50000 Node.val 1000
思路解析
准备阶段 首先我们需要一个哑节点dummy node来简化头节点的处理。哑节点是一个不存储实际数据的节点它的next指针指向链表的头节点。这样我们就可以避免处理头节点翻转时的特殊情况。初始化三个指针prev前一个子链表的末尾节点、curr当前子链表的开始节点和end当前子链表的末尾节点。开始时prev指向哑节点curr指向头节点。循环处理阶段 在每次循环中我们首先使用getKthNode函数找到当前子链表的末尾节点end。如果end是null说明剩下的节点数不足k个我们不需要再翻转直接结束循环。如果end不是null说明当前子链表至少有k个节点可以进行翻转。在翻转之前我们需要保存下一个子链表的开始节点即end.next因为翻转后我们会丢失对它的引用。使用reverse函数翻转当前子链表。翻转后curr原来的开始节点会变为翻转后的末尾节点并且它的next指针会指向下一个子链表的开始节点。更新prev和curr的位置。prev指向curr翻转后的末尾节点curr指向下一个子链表的开始节点即之前保存的end.next。结束阶段 当循环结束后我们得到了一个每k个节点一组翻转后的链表。这个链表的头节点是哑节点的next指针所指向的节点。返回哑节点的next指针作为结果。
Java代码示例
public class ListNode { int val; ListNode next; ListNode(int x) { val x; }
} public class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } // 创建一个哑节点(dummy node)简化头节点处理 ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; // 前一个子链表的末尾节点 ListNode curr head; // 当前子链表的开始节点 while (curr ! null) { // 计算当前子链表的末尾节点 ListNode end getKthNode(curr, k); if (end null) { // 不足k个节点无需翻转直接退出循环 break; } // 翻转当前子链表 ListNode nextGroup end.next; // 下一个子链表的开始节点 end.next null; // 切断当前子链表与后续链表的连接 prev.next reverse(curr); // 翻转后的子链表连接到前一个子链表的末尾 curr.next nextGroup; // 翻转后的子链表的末尾节点指向下一个子链表的开始节点 // 更新指针 prev curr; // 前一个子链表的末尾节点移动到当前翻转后的子链表的末尾 curr nextGroup; // 当前子链表的开始节点移动到下一个子链表的开始节点 } return dummy.next; // 返回修改后的链表头节点 } // 翻转链表 private ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; // 返回翻转后的头节点 } // 获取第k个节点 private ListNode getKthNode(ListNode head, int k) { ListNode curr head; for (int i 0; i k curr ! null; i) { curr curr.next; } return curr; }
} Python代码示例
class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def reverseKGroup(self, head: ListNode, k: int) - ListNode: if not head or k 1: return head # 创建一个哑节点(dummy node)简化头节点处理 dummy ListNode(0) dummy.next head prev dummy # 前一个子链表的末尾节点 curr head # 当前子链表的开始节点 while curr: # 计算当前子链表的末尾节点 end self.getKthNode(curr, k) if not end: # 不足k个节点无需翻转直接退出循环 break # 翻转当前子链表 next_group end.next # 下一个子链表的开始节点 end.next None # 切断当前子链表与后续链表的连接 prev.next self.reverse(curr) # 翻转后的子链表连接到前一个子链表的末尾 curr.next next_group # 翻转后的子链表的末尾节点指向下一个子链表的开始节点 # 更新指针 prev curr # 前一个子链表的末尾节点移动到当前翻转后的子链表的末尾 curr next_group # 当前子链表的开始节点移动到下一个子链表的开始节点 return dummy.next # 返回修改后的链表头节点 # 翻转链表 def reverse(self, head: ListNode) - ListNode: prev None curr head while curr: next_node curr.next curr.next prev prev curr curr next_node return prev # 返回翻转后的头节点 # 获取第k个节点 def getKthNode(self, head: ListNode, k: int) - ListNode: curr head for _ in range(k): if curr: curr curr.next else: return None return curr
